Dartmouth Professor Peter Winkler visited our department yesterday and
today, the first stop of a two-week five-university tour. Winkler
gives great seminar talks and is easy to talk to about hard combinatorial
problems. Unfortunately whenever I see him he also brings very tantalizing
puzzles that you have to work hard at not thinking about, lest they
consume you. For example
Love in Kleptopia
Jan and Maria have fallen in love (via the internet) and Jan wishes to
mail her a ring. Unfortunately, they live in the country of Kleptopia
where anything sent through the mail will be stolen unless it is
enclosed in a padlocked box. Jan and Maria each have plenty of
padlocks, but none to which the other has a key. How can Jan get the
ring safely into Maria's hands?
From
Seven
Puzzles You Think You Must Not Have Heard Correctly (with
solutions). For the more mathematically minded here is the
Infinite
Hats Problem that he told me earlier this year.
A countable number of people each have either a white hat or black hat
on their heads. Each person can see everyone's hats except their
own. Each person simultaneously announces a guess for the color of
their hat. Is there a strategy for the people so that no matter what
the arrangement of hats, only a finite number will incorrectly guess
their hat color?
For more check out his book
Mathematical Puzzles: A Connoisseur's Collection
.
It's a great puzzle book, with a tilt towards discrete & algorithmic math puzzles that will suit computer scientists.
ReplyDeleteI believe Winkler is also the originator of cryptographic bidding in bridge: partners generate a shared secret, and use it to disguise the meaning of their subsequent bids. It's now banned, on the principle that bids should have a 'clear meaning', but the basic strategy is algorithmic and can be disclosed to the opponents without compromising its effectiveness. (Have I got this right? I'm a casual player.) Anyway, he seems like a cool guy.
Depending on your theory of padlocks, there's a solution to the padlock problem much simpler than either of the ones mentioned by Peter. First Maria sends Jan an unlocked box with one of her padlocks attached to it; then Jan puts the ring in the box, locks it, and sends it back to Maria.
ReplyDeleteHere I'm assuming (1) that Jan can *lock* Maria's padlock without a key, and (2) that the padlock itself isn't going to be stolen.
Are these assumptions obviously worse than the assumption that padlocks can be "doubled up," or that a key can be attached to the hasp of a padlock?
(If we continue the cryptographic analogy, the padlock that Jan can lock but not unlock is basically a trapdoor OWF...)
I don't like Peter's second solution to the padlock question (Attach a key to the first padlock, then send the second box locked with the corresponding lock). If the mailman steals both boxes, he can get the ring.
ReplyDeleteScott's solution may suffer from an attack where more than just the padlock is stolen:
ReplyDeleteIf the klyptos replace the padlock in the box with their own padlock (for which they have the key). Then when Jan mails the ring (secured with the insecure padlock), it will be stolen!
There is no solution to this problem, since anything sent through the mail will be stolen.
ReplyDeleteI think this is how Jan can send the ring safely to Maria.
ReplyDeleteFirst Jan sends the ring in a padlocked box to Maria. Maria, then returns the box, by adding her own lock to the box as well. (now the box is locked with two locks.
Jan then receives the box with two locks, removes his lock and then returns the box back to Maria, which is locked with Maria's lock only and she can open it easily and can get the ring.
ashutosh.
Isn't the multiple-padlocks thing the same idea as what Diffie-Helman key exchange does?
ReplyDeleteYou'r right about the D-H key exchange, Anon#7 -- aravind srinivasan
ReplyDeleteThere is something strange with the infinite hats problem, because it seems so implausible that all but a finite number of players can guess correctly, that the puzzle makes sense only if the answer is yes, they can do that, and the solution is clever but simple.
ReplyDeleteBut suppose that there is an algorithm that solves the infinite hat problem, and suppose that, for every k, the set of hat assignments that yield k errors or fewer is measurable. Then let's look at the probability that there are at most 1 error, 2 errors, ..., k errors, ...
These probabilities form a monotone sequence that converges to one, so there must be a large enough k0 such that, on a random hat assignments, there is at least a 90% probability that no more than k0 errors occur. But look at the first 4k0 players: in particular, on a random hat assignments, there is a probability at least 90% that no more than k0 errors occur among the first 4k0 players. So the average number of errors among the first 4k0 players is at most 1.4*k0. Every player, however, has error probability 1/2, and so the average must be 2k0.
It is compatible with the negation of the axiom of choice that every subset of the unit interval (and so every set of infinite binary strings) is measurable, so a solution to the infinite hats problem must make essential use of the axiom of choice. How can a simple and clever solution use the axiom of choice?
How can a simple and clever solution use the axiom of choice?
ReplyDelete*** SPOILER WARNING ****
The axiom of choice is used to pick representatives for equivalence classes of P(N) mod finite symmetric difference.
*** END SPOLIER ***
Luca's proof is nice though because it is actually consistent that directed choice holds and every set of reals is measurable. So this shows the solution uses a lot of the power of choice.
I guess it should be pointed out that the consistency of all sets of reals measurable without choice does have very mild large cardinal assumptions.
ReplyDeleteBack in fall 2004, when I was a TA for Berkeley's undergraduate algorithms course, I was looking for a way to explain RSA to the students. In the end, I described an analogy similar to Scott's solution. I'm curious, is this a standard analogy for describing RSA?
ReplyDelete-Henry
what does P(N) mean ?
ReplyDeletewhat does P(N) mean?
ReplyDeleteThe power set of N (N = the natural numbers).
I'm curious, is this a standard analogy for describing RSA?
The analogy that Adi Shamir used when I took his Crypto course at U Chicago was a box with two openings, each independently lockable. Maria sends an empty box to Jan with her lock on one of the openings. Jan puts the ring in the box with the other opening, locks it with his lock, and sends it to Maria, who then unlocks her lock on the other opening and removes the ring.
This is really just an example to show that two parties can communicate secretly without ever sharing a secure channel.
By the way, Winkler's puzzle book is great. My current favorite, because it is so easy to state, is "Can 3-space be partitioned into circles?"
thats not really a spoiler.
ReplyDeletecan you solve the hat problem please ?
ReplyDeleteHm, the solution to the hat problem seems to involve the players being able to remember an uncountably infinite number of infinite bit-vectors going into the game. I don't like it, although I guess its not such a huge stretch, given that they can apparantly observe a countably infinite set.
ReplyDeleteAnother sweet puzzle in the book (slightly generalized):
ReplyDeleteAlice is about to communicate an n-bit message to the world via public radio broadcast. The radio operator Alice hires, Steve, is a spy, who wants to covertly communicate to his handler Hannah. The radio system is error-free, but Steve figures he can safely modify one bit of Alice's message and attribute it to error.
Steve and Hannah want a protocol where Hannah can interpret the broadcast to read off some info encoded by Steve. Neither party knows anything about what Alice's message will be beforehand.
Clearly Steve can transmit, say, 1 bit of info by modifying the message's first bit.
Can Steve transmit some t(n) bits of information, where t(n) goes (slowly) to infinity as n does? Again, only one bit-flip allowed!
Does Steve have to flip a bit? Can he leave Alice's message unchanged?
ReplyDeleteOn comment Anon#6
ReplyDelete(now the box is locked with two locks....etc.
What if in the first round of the protocol i.e. from sender to receiver - mail-man returns the box by putting his lock before it could even reach Maria?
Steve can leave the message unchanged, yes.
ReplyDeleteThat solution (a) explains what AC is needed for far, far better than the typical examples do (which generally don't need AC, at least not the ones given to non-mathematicians in not really set theory classes), and (b) convinces me that AC is a bunch of bullshit.
ReplyDeleteThat solution (a) explains what AC is needed for far, far better than the typical examples do (which generally don't need AC, at least not the ones given to non-mathematicians in not really set theory classes), and (b) convinces me that AC is a bunch of bullshit.
ReplyDeleteI think this makes clear why the axiom of choice is silly in a situation where you want to construct something. But this problem is ludicrous as a construction -- you're talking about INFINITELY MANY PLAYERS who all get the information of all others, and then choose. So the strategies possible here are all ludicrous. There's a difference between believing something exists and that their's a way to find it.
Anonymous--even when all strategies must be infinite, there are still 'degrees of ludicrousness', and it's still worth thinking whether a less ludicrous strategy is possible.
ReplyDeleteThe solution given requires an uncountably infinite amount of information to specify the choice function. Luca's argument implies there isn't even a countably infinite strategy, in the sense of a strategy for the players where each player j's hat-guess is the output of a countably infinite boolean circuit C_j over the colors of the other players' hats, where we allow gates to have infinite fan-in.
For such circuits the hat-sequences causing k or fewer errors would be Borel (right?) & measurable for all k, contra Luca's proof.
So, how can we describe the information content of AC over the reals? It's greater than that of the Halting set, say (which is just countable), and is good for certain hat-tricks, yet it's filled with what seems like nonsense.
So, how can we describe the information content of AC over the reals? It's greater than that of the Halting set, say (which is just countable), and is good for certain hat-tricks, yet it's filled with what seems like nonsense.
ReplyDeleteNo offense to Andy, but I read these couple sentences over many times and still don't understand the point they're trying to make.
Well, I was trying to ask an open-ended question. But let me try to expand my starting observations.
ReplyDeleteFirst let me point out something about oracle Turing machines. If you pick an oracle A uniformly at random, A will be an incomputable language with probability 1, and feeding the oracle to our Turing machines will increase their power, allowing them to compute, e.g., A itself.
On the other hand, say L is any fixed incomputable language. It's a fact that with probability 1 over A, L will stay incomputable even given oracle access to A.
So we expect to get new decision power from A, but not any power we can predict in advance. It seems a little useless.
Now 'scaling up' to the model of countable-sized circuits with infinitely many inputs, or some related model of computation, I expect that oracle access to a 'random' function F from infinite bitstrings to {0, 1} (or, to infinite bitstrings) behaves the same way: it enlarges the sphere of the computable, but we can't predict how.
So my question is, what if we're given the promise that the function F we receive is a 'choice function', i.e. it maps all strings in an equivalence class modulo finite symmetric difference to the same representative for that class (or, maybe it could perform some other task that makes essential use of the axiom of choice)?
Is there a function G that has countably-infinite circuit complexity given oracle access to any such F, but not without it? Or is the mere promise of a choice function too weak?
This is one sense in which I want to ask about the information content of the Axiom of Choice.
the solution is so unconstructive, that the answer is basically the question. In the first place, i thought, obviously no locale strategy will work, so a single person will have to refer to all other "hats".
ReplyDeleteokay ..
question:For a given countable configuration only a constant may guess wrong.
answer: everybody memorize all countable configurations minus constant difference.
.. i wouldn't call that a strategy.
Second question: assuming that there is no such G (that would be my guess) how to characterize the positive contribution a choice function would make to countable-sized resource bounded agents?
ReplyDeleteContinuing to think of a choice function as being 'like' a random function, what is suggested? Random bits are provably useful in solving various coordination problems and disseminating information among networks of agents (see e.g. Nancy Lynch's textbook).
Similarly, Winkler's puzzle shows how the axiom of choice can be used to pool distributed info (sort of) in an infinite setting. So how far does the analogy extend?
If the hat assignment is algorithmically random and there's a strategy to guess all but finitely many of its bits, then that seems like a problem.
ReplyDeleteThe axiom of choice is not actually used to get a choice function, you can do that with no problem, really. Such a function will be a class, but without AC you can't prove it's a set (i.e. it may be a proper class). The content of the axiom is that there's a
choice function that's a set.
The axiom of choice is not actually used to get a choice function, you can do that with no problem, really. Such a function will be a class, but without AC you can't prove it's a set (i.e. it may be a proper class). The content of the axiom is that there is a choice function that is a set. Or equivalently, that it's range is a set.
ReplyDeleteAnother way to see there's no such strategy (we might not require a strategy to be a TM), is to notice that for each arrangement of hats a player sees, there are two possibilities for the color of his hat. The information available to him will be the same in both cases, so his chances of a correct guess are only 50/50.
ReplyDeletesee my web page about the negation
ReplyDeleteof the axiom of choice
http://jebara.topcities.com
Adib Ben Jebara.