Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Hmmm...many duplicates got under my guard.

I've tried to eliminate them all, and am now getting 2041 as the answer.

Still checking my work, though...

Hi evene;

You use the 'hide' tags.

In the following two examples I've included a space before "hide" in the opening tag. You must remove that space in each example for them to work for you, but their inclusion enabled me to prevent my text from turning into hide boxes.

This:

[ hide=Hint]Type your text here...[/hide]

will give you this:

And this:

[ hide]Type your text here...[/hide]

will give you this:

Click on the two boxes to display their contents.

If you click on the "Quote" button in the bottom right-hand corner of my post you'll see exactly how I did it for my two boxes.

You can also just copy my examples into your post and experiment there.

Thanks!

I generated the list of 80730 combinations in M and pasted it into an Excel spreadsheet, which I used for the rest. That was the least time-consuming option for me.

Hi;

Here are images of the 54 solutions, displaying one solution per row.

The 5 tries were applied in ascending order, and the images display the progress.

Thanks! I'll take off my dunce cap, then!

Well, surprise, surprise! Here I was thinking that 9 would win, but it looks like 5 wins...as Anna thought it would.

I found 54 different combinations (listed below) that 'will' open the lock on the fifth try.

I say 'will', because I haven't tested them all...although the 10 random combinations I tried all worked. The other 44 should too, because all 54 were found by the same program.

Each set of codes will open the lock irrespective of the order in which they're tried.

```
111 122 212 221 333
111 122 233 312 321
111 123 213 221 332
111 123 232 313 321
111 132 212 231 323
111 132 223 312 331
111 133 213 231 322
111 133 222 313 331
111 222 233 323 332
111 223 232 322 333
112 121 211 222 333
112 121 233 311 322
112 123 213 222 331
112 123 231 313 322
112 131 211 232 323
112 131 223 311 332
112 133 213 232 321
112 133 221 313 332
112 221 233 323 331
112 223 231 321 333
113 121 211 223 332
113 121 232 311 323
113 122 212 223 331
113 122 231 312 323
113 131 211 233 322
113 131 222 311 333
113 132 212 233 321
113 132 221 312 333
113 221 232 322 331
113 222 231 321 332
121 132 213 322 331
121 132 222 231 313
121 133 212 323 331
121 133 223 231 312
121 212 233 313 332
121 213 232 312 333
122 131 213 321 332
122 131 221 232 313
122 133 211 323 332
122 133 223 232 311
122 211 233 313 331
122 213 231 311 333
123 131 212 321 333
123 131 221 233 312
123 132 211 322 333
123 132 222 233 311
123 211 232 312 331
123 212 231 311 332
131 212 223 313 322
131 213 222 312 323
132 211 223 313 321
132 213 221 311 323
133 211 222 312 321
133 212 221 311 322
```

anna_gg wrote:

Compose a strategy to find the minimum number of tries to open the lock, under the worst situation and prove that this strategy is optimal.

My strategy was to do a brute force search of the 80,730 possible combinations of 5 choices from 27 (the maximum number of different guesses possible), which was successful. To make sure that 5 was the minimum number, I also tried 3 and 4, but no luck there. Not very elegant; but then, neither am I!

I think a good strategy now would be for the lock operator to memorise one of the solutions, and here I'd recommend {112,121,211,222,333} as being one of the easier sets to remember, because it comprises the two triplets {2,2,2} and {3,3,3}, and the three permutations of {1,1,2}.

Having taken so long to properly understand both the problem and Nehushtan's method (and also because there are so many solutions!), I feel a little uneasy about the result, so someone please check a few of the combinations and let me know how they performed.

Thanks!

anna_gg wrote:

...it can be done in 5 guesses, if you pick some other sets instead of the triplets. Maybe this way we manage to eliminate all 6 of the remaining combinations.

I tried a dozen or so combinations, and they all worked like the triplets in eliminating 21 options as long as they contained, in total, three 1's, three 2's and three 3's. The six remaining options in my tries didn't appear to be able to eliminated other than singly.

Yes, there are 80,730 (only) combinations of 5 guesses from the total of 27 - and I've saved the list in Excel and M - but I haven't been able to devise a program to do what we need.

Other numbers of guesses and combinations:

6 guesses from 27 options = 296,010 combinations;

7 guesses from 27 options = 888,030 combinations;

8 guesses from 27 options = 2,220,075 combinations;

9 guesses from 27 options = 4,686,825 combinations...which are very quickly reduced by Nehushtan's strategy and mine.

Hi Nehushtan;

Thanks for your explanation...I finally got it! Your method works perfectly well.

I'm very sorry about having dragged you through this for so long before the penny dropped for me!

Hi Nehushtan;

Leaving aside the theoretical approach for a bit, I'd now like us to put your method to a practical test...just to dispel any doubts I may have about it working.

I happen to have a combination lock identical to anna_gg's, but unfortunately I don't know the code to open it. So I'd like you to post, in this thread, the codes that will open the lock in a number of tries not exceeding the maximum number you mentioned in posts 2 and 11.

Now, I should let you know in advance that this is a tricky little lock that employs strict avoidance tactics to ensure a worst-case scenario - just like the puzzle's lock!

You can post any number of codes at a time, their quantity not exceeding the maximum number you've stated...although, just out of curiosity should that maximum be reached without success, we could continue until the lock is opened to see how many extra tries it may take. Up to you.

I'll try the codes on the lock in the order that you post them, and then respond with progress reports about their success (or otherwise) as we go.

Your turn...

Nehushtan wrote:

Yes.

Ok...sorry about that.

Nehushtan wrote:

No.

Oh, I see.

Hi Nehushtan;

Nehushtan wrote:

Read the thread!

I may have misunderstood something here.

Are you saying that if the correct combination is 123 (with wild's position unknown), and you entered 111, 112, 131, 132, 211, 212, 213, 221, 222, 231, 232, 233, 311, 312, 313, 321, 322, 331, 332, and 333 (none of which will open the lock, as I understand it) before using one of the seven successful combinations you listed in post #5, that your method still holds?

This is my post #9 method:

Subject to the rule "each question must be chosen by exactly 2 students", there are 2220 different sets (permutations) of first-choice questions, and any set chosen determines which question numbers (but not their exact order) form the set of second-choice questions. No student has the same two questions (not exactly stated, but implied, I'd say).

Here's an explanation of the table below:

The first-choice questions only have three varieties (v1, v2, v3), and their second-choice partners the same. Examples are given.

There are different quantities of these varieties: v1=120, v2=1200, v3=900, which total 2220.

The number of permutations of second-choice questions is constant for each of the varieties: v1=44, v2=32, v3=24.

So now we can calculate the total number of different possible ways the questions can be picked:

v1 + v2 + v3 = (120 x 44) + (1200 x 32) + (900 x 24) = 5280 + 38400 + 21600 = 65280

But half of the combinations of first and second-choice sets are duplicates (eg, 1st choice 1,1,2,3,4 & 2nd choice 4,5,5,2,3 = 1st choice 4,5,5,2,3 & 2nd choice 1,1,2,3,4).

Therefore the answer is 65280/2 = 32640.

```
1st choice | 2nd choice
A B C D E | A B C D E varieties 2nd choice perms varieties x perms
v1: no repeat digits 1 2 3 4 5 | 2 3 1 5 4 120 44 5280
v2: 1 pair of repeat digits 1 1 2 3 4 | 4 5 3 2 5 1200 32 38400
v3: 2 pairs of repeat digits 1 1 2 2 3 | 5 4 3 4 5 900 24 21600
Totals 2220 65280...less 50% duplicates = 32640
```

From the way I've spaced the circles vertically, the image shows the top row of lights right at the top of the square. However, if spaced at the minimum amount there is a vacant strip of 4√0.75 across the top. Too small to do anything with, I suppose...but I did have a look to see if I could combine it somehow with other unused spaces to conjure up another spotlight, just in case this puzzle came from some sneaky puzzle setter!

For that I tried diamond shapes and equilateral triangles, but gave up after a while.

Hi;

I've found 20:

Ok...thanks.

This is how I arrived at my answer of 32640. It's a method I thought up just yesterday to verify the result from my post #9 method (which it did), but is easier to explain than that one.

There are 113400 permutations of the two lots of 5 questions, starting with 1,1,2,2,3,3,4,4,5,5 and ending with 5,5,4,4,3,3,2,2,1,1.

In each permutation, student A's questions are the first two digits, B's are the next two...and so on for C, D & E.

Of the 113400 permutations, there are 65280 where no student chooses the same two questions.

65280 is comprised 50:50 of valid possibilities and duplicates: eg,

```
A | B | C | D | E
First valid possibility (#2528) : 1,2 | 1,2 | 3,4 | 3,5 | 4,5
Its duplicate (#23348) : 2,1 | 2,1 | 4,3 | 5,3 | 5,4
Last valid possibility (#90053) : 4,5 | 4,5 | 2,3 | 1,3 | 1,2
Its duplicate (#110873): 5,4 | 5,4 | 3,2 | 3,1 | 2,1
```

So the answer = 65280/2 = 32640.

That took miles of coding in Excel (also with a bit of help from M), for which you'd need a 64-bit version of Excel running on a 64-bit operating system with a truckload of ram...all of which my computer has, fortunately.

No doubt there's a tiny mathematical formula hiding out there somewhere that could solve this in less than a blink!

Hi anna_gg,

anna_gg wrote:

In how many possible ways can this be done?

Is this an example of two different ways?

```
1 2
A: 1,3 1,3
B: 1,4 1,3
C: 2,4 2,4
D: 2,5 2,5
E: 3,5 4,5
```

It seems so to me, and my answer in post #10 is based on this example being valid.

Thanks for the offer, but I think I'll pass...for a while at least.

I have so many unfinished projects at home that I should be doing at a quicker rate than I have. As is the case with many owner-built houses - which mine is - I've left a lot of jobs till later. And now it's later!

Wow - hardly gave me time to blink!! I don't understand it, of course. Waaay over my head!

Oh, well...coding up a working sim was satisfying enough for me. It didn't take me long to sack Excel and let M take over.

M rolled the die at about 58000rps compared to Excel's 4000rpm, but Excel had to wade through updating spreadsheet cells, whereas M just counted under the table.

My code for 1 billion rolls took M 4.75 hours. I know a maths way is quicker than a sim, but I couldn't think of one...and I've never heard of a Markov chain.

What's the quick M way?

So that's a difference of about 6.76% from my last M simulation.

Maybe I should have let M keep rolling the die till now, and I might have got closer to the right answer!

Is the answer 32640?

*EDIT: It's based on the post #9 info.*

Well, by my reckoning, there are 2220 different sets of first-choice questions, and the set chosen will determine which questions will form the set of second-choice questions...of which there will be varying numbers of permutations.

That's as far as I've got...

*EDIT 1: I think the 2220 should be halved to 1110 to avoid choice-order duplicates where second-choice sets have already been used as first-choice sets.**EDIT 2: "...of which there will be varying numbers of permutations." There are only 3 such varieties: 24, 32 and 44. *

Likewise me!