Find Your Name
May 13th, 2007
A Hint
First, if you came to this page because you have given up on the riddle before solving it, here is a little hint, in case you want to try it some more:
Observe that the men don’t have to decide which boxes they will open before entering the room! They can select which boxes to open based on what they saw in the ones already opened!
The Solution
The men first decide upon a random one-to-one matching from their names to the numbers 1-100 (this selection being random, eliminates possible efforts from the part of the organizer of the boxes to fail the system). They do a similar matching with the boxes.
So now we can refer to the men and boxes by numbers – we have man_1 to man_100 and box_1 to box_100.
Now, the algorithm of the men is as follows:
man_i first opens box_i. In it he finds the name of man_j. He then opens box_j, and so forth (up to a maximum of 50 boxes).
What are the chances of the men to succeed? Notice that the boxes generate a permutation P on the numbers 1-100, as such:
P(i) = j, if the name inside box_i is that of man_j
Now, the men will all succeed i.f.f. the permutation P does not contain a cycle of length greater than 50. Lets calculate the probability that no such cycle exists.
D = #{ P is a permutation of 100 elements } = 100!
Nk = # { P is a permutation of 100 elements | P has a cycle of length exactly k } = 100!/k
Notice that if k > 50, there can be at most one cycle of length k in P and so:
Prob(P contains a cycle of length k) = Nk/D = 1/k
So the probability of no cycle of length greater than k (assuming k >= 50) is:
Prob(P does not contain a cycle of length greater than k) = 1 - 1/(k+1) – 1/(k+2) – … – 1/100
Or, otherwise, taking k = 50:
Prob(no big cycle) = 1 – 1/51 – 1/52 – … – 1/100 = 1 – H(100) + H(50) = 1 – (H(100)-H(50))
Where H(n) is the n’th harmonic number. It is well known that H(n) is about ln(n) (in fact, it is a bit larger).
We get:
Prob(no big cycle) =~ 1 – (ln(100)-ln(50)) = 1 – ln(2) =~ 0.31
Pages: 1 2
May 18th, 2007 at 9:33 am
I want to make sure about one important detail of the riddle – you said “Each of the notes with the names is put in a different box randomly” – is it truly random, or is the person arranging the names in the box allowed to be “evil” and put them in such a way as to fail the men’s strategy?
If the names are put in the boxes randomly, then I solved it!!!
What a cool riddle.
I want to comment about the solution, but is there any way to put text in spoiler tags? I don’t want to ruin the solution for people reading the comments…
May 18th, 2007 at 9:41 am
Update for my last comment. My first question was irrelevant. The same solution works even if an evil genius arranges the names in the boxes.
May 18th, 2007 at 3:24 pm
Hi Matan,
First let me congratulate you for being the first person to comment on my site.
You raised an interesting question, and I still have to decide how I want solutions to be posted. I think what I will do is publish a “solution post”, which will be password protected with a known password (such as “solution”). That way everyone will be able to see the solutions but no one will see them accidentally.
Anyway, I am going to wait for a couple of weeks since the time I publish a riddle and the time I publish its solution (otherwise the temptation to read the solution is to big).
May 22nd, 2007 at 5:32 pm
Well, without meditating on this one too much, I believe I have the algorithem. I’d ask here if I’m in the right direction, but that would be spoiling, now wouldn’t it?
guess I’ll check my constants and get back to you.
May 23rd, 2007 at 10:25 pm
Elad, a friend of mine, complained that the riddle is not that hard. Well, I might have exaggerated about the difficulity level. The puzzel is solvable. I only meant to say that it is harder than all the riddles posted before it (those of you with good perception might notice that only the Ants riddle was posted before it
).
I also like the “Warning! Very Hard!” logo, and I think I’ll keep it.
Anyways – if it is too easy for you, you can always try to solve it with 1000 men instead of 100!
September 23rd, 2007 at 10:05 am
Actually, I fail to see how *any* algorithm works if an adversary who knows the algorithm sets up the notes. I’d for instance, just set P(x) = x + 1 mod 100, which would render everybody quite dead. So I think I’d actually like to hear Matan’s solution.
I came up with something a little bit better, where the secret relies not on the whole algorithm – the men come up with a random permutation of their own, let that be h, and rather than following P, they follow P*h. The same calculation applies and they have 30% chance of saving, but this time they can tell the adversary the algorithm, but they need to keep their permutation secret (kind of like Kerkhoff’s cipher design rule).
September 23rd, 2007 at 7:24 pm
Srul,
As I explained in the solution above: “The men first decide upon a random one-to-one matching from their names to the numbers 1-100 (this selection being random, eliminates possible efforts from the part of the organizer of the boxes to fail the system). ”
I think this is exactly what Matan meant (and if I understood you correctly then its what you mean as well).
My view of this is a little different (instead of saying the men have a shared secret, I say the algorithm uses random – kind of the same). The men have no apriori secret (i.e. the adversary knows everything in advance) but the algorithm’s first step is “generate a random permutation”.
Kind of a philosophical issue…
September 23rd, 2007 at 9:21 pm
You understood correctly. In my notation P(x) is the number of the man written in box x, then P is a permutation.
Well, if the algorithm says “generate a random permutation” in the beginning, everybody will draw independently (not the same h by my notation), and have %30 chance of drawing no big cycles. Therefore it would require for all P*h to have no big cycles which would happen with probability of (0.3)^100. And if it’s not independent (i.e. an Oracle draws them together the same random permutation) that’s information sharing.
You could deviate the question a bit by saying that the people are allowed to pass information of some size, let’s say X bits. Then the solution would be, generate 2^X random permutations (apriori, known to everybody including adversary). Then the first man draws a number between 0 and 2^X-1 and transmit that number (exactly X bits). Then everybody knows which permutation to use. I wonder what’s the minimal X so that the adversary cannot screw up permutation f*h for all possible h.
Great riddle overall!
September 23rd, 2007 at 11:51 pm
Srul,
I meant that the people run the algorithm together. I understand if you want to call that cheating.
I think that adding this “generate a random permutation” part improves the more naive algorithm of “use the following given permutation…” (as obviously the adverdary can arrange the boxes in such a way as to fail their system).
I agree that letting all the men generate a random permutation together is similar to having a pre-shared secret.
And yes – It is a great riddle!
November 29th, 2007 at 7:27 am
greatings
nice