Puzzle : Secret Sharing

Comparatively, simple puzzle today. Again, thanks to ramprasad.

A king was dying. (There is something about puzzles woven into a story, it makes it more dramatic 🙂 ) He alone knew the key to the secret treasure. He had N sons ( anything can happen in a puzzle! ). He wanted to pass on this secret key to his sons. Passing the key in its entirety may become reason of a quarrel. Let us say that key is a very large number ( or a large binary string ).

1) He want to make sure that only when all of his sons combine their part of the key, can they open the treasure.

2) He want to make sure that any k out of N can combine their keys to open the treasure, but any set of k-1 keys can not open the treasure.

Solution :

1) First is extremely simple. Let us say string S is the secret. Generate N-1 random strings of the same length as S. Create Nth key such that XOR of all the keys gives S. Done. Without all N keys, treasure can not be opened as they have to find S from possible strings.

2) Second is also easy. It was an aha moment, when ramprasad told me the general strategy to design such a secret sharing mechanism. Let us say, you want to make sure that any k out of N son can open the treasure. Let us say the number S is the secret. Generate a random polynomial f(x) of k-1 degree such that f(0) = S. Or in other words, S is the constant in the polynomial. Now the part of the keys are nothing but evaluation of the polynomial at some random points ( of course, not at 0 ). Given any k-1 points, there can be infinitely many k-1 degree polynomial which can pass through these points. However, for any given k points, a unique k-1 degree polynomial can be determined.

Well, there you go, so easy eh?

Puzzle : Black and white hats revisited, .. yet again!

The credit for this puzzle again goes to ramprasad. And I think that for coming days he will add a lot to my knowledge and blog as he got hold of peter winkler’s book on puzzles.

As usual, there are n people ( finite this time ). Black and White hats are randomly placed on each of them. They have to give their answer simultaneously and they have no means of communicating with anybody else.

1) In this puzzle, every one must guess the color of their hat. Come up with a strategy so that every one guesses the color correctly with probability 1/2 ( and I think this is the best you can achieve ).

2) In this variation, people are allowed to guess or say “pass” ( basically saying they do not want to guess ). Group of people will succeed if there is at least one person who has guessed the color of his/her hat correctly, and none of the persons guesses it wrong. What is the strategy to follow so that you can maximize the probability of success??

Solution :

1) I could get the solution of this problem after a bit of pondering. Let ‘1’ stand for black and ‘0’ stand for white. Everybody will assume that the summation of the entire string is 0 mod 2. So a person sums up from all the hat he/she sees and then choose the color so as to make the grand total 0 mod 2. Given any random strings from , the probability that the total of the string is 0 mod 2 is 1/2.

2) Two is a bit tricky and I could not get it. Let us try for n=3. The strategy would be that if a person sees the same color on the other two, then he guesses the opposite color otherwise he will pass. It is easy to see that they will fail only when the string is 000 or 111. Probability of suceess is 3/4.

In general, for n people, they can come up with some “Perfect Code” ( Just google it, will ya? ). Code with hamming distance 3 and error correcting capability of 1 bit. Now, a person sees the remaining part of the string, if by guessing ‘0’ the string falls into the code, he/she will guess ‘1’ and vice versa. Otherwise, the person will pass. One can see that the experiment will fail when the assigned string is one of the string in the code. In all other cases, the person, flipping whose bit makes the string fall into the code, guesses it right and rest all will pass. But then there are n times more strings, which are hamming distance one away from code. So the probability of failure would be O(1/n).

Sorry for the shaddy explanation, but believe me, it works!

 

Related post : here and here

Puzzle : Black and White Hats Revisited

Well,
I have been very lazy and irregular these days so I am not even trying to commit that I will be so in future :-). Here are two very nice puzzles, thanks to Ramprasad.

Problem : A person is standing on each natural number belonging to N. Yes, that means that there are countably infinite people standing in a straight line 1,2 …..infinity. As always, black or white hats are placed on each of them. This gives rise to a random string of infinite length. A person can see everybody else’s hat but not his/her own. Everybody has to guess the color of their hat simultaneous. No communication between any two people is allowed.

1) Come up with a strategy so that infinitely many people guesses the color of their hat correctly.

2) Come up with a strategy so that only finitely many people guesses the color of their hat incorrectly.

Solution :

Well, 1st puzzle is comparatively easy to solve. I will give two solutions, here
1a ) This solution is by deepanjan. A person standing on position p, looks towards infinity and see if he/she sees any black hat. If he/she sees a black hat, the person will announce that his/her hat is black. Otherwise announce that his/her hat is white.

Why would it work?
Let us say, there are only finitely many black hats placed. In such a case, there must be a largest position bp such that for all position greater than bp, hats are white. In such a case, all people standing on position greater than bp will look towards infinity and will see no black hats so they will announce their hat as white. Hence, infinitely many people guessed the color of their hat correctly.

What if black hat appears infinitely often? In that case, any person with a black hat, would be able to see another black hat when he/she looks towards infinity. Hence, all persons wearing a black hat will guess it right. Again, they are infinitely many of them.

1b) A person on position 2p-1 will pair up with person standing at position 2p. Let us call them p1 and p2. p1 will guess the color of his/her hat to be the same as p2. p2 on the other hand will guess the color of his/her hat to be different than p1. Obviously, one of them has to be right. Meaning, half of the people will guess it right.

2) Solution for two is tricky. It is based on “Axiom of Choice”.

Let us say two infinite strings s1 and s2 are related, if they are finite hamming distance away from each other. Such a relation is equivalence relation, hence partitions the set of all strings into equivalence classes.

Let these classes be c1,c2,…ck. So basically, any two strings drawn from a class ci will be finite hamming distance away from each other. For each such class ci, people will fix some representative string si belonging to ci.

Now, a person p looks at given infinite string pi. The actual assignment might be given by string S. A person may put 0 or 1 as a guess for his own hat and still both the resulting strings will be in the same class as S and pi. So, having observed a string pi, a person identifies the class ci in which pi belongs, and picks up corresponding representative string si. He announce the color of his/her hat as given by si. Because, si is only finite hamming distance away from S, only finitely many people will guess it wrong.

Phew, did not know that innocuous looking “Axiom of Choice” could be so powerful mathematical tool.