![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyMichigan seems pretty cool. And I will of course not write anything substantive. About Michigan, I mean. Expect me to write about some puzzles people started talking about...
I briefly ran into ADan, he certainly wasn't expecting to see me. Also, I did not realize Brian Conrad teaches there, so when I saw him at first I was like "Why is Keith Conrad here?" before I realized it had to be Brian Conrad (which it was).
Also a prospective student[0] with me was Dave Putnins, back from BCA. I actually completely failed to recognize him. He's graduating in 3 years from Oxford (apparently it's usually only 3 years at English schools?). Funny thing, once it got to be nighttime, he kept making comments about how he was tired because he just flew in from England. But it wasn't until quite late that somebody heard this, listened to the voice he was saying it with, and responded, "Wait, you're not from England, you're from New Jersey!"
One of the professors I talked to, deBacker, was a student of Sally, and instead of finding much of anything out about Michigan we more or less just ended up comparing the Chicago professors when he was there vs. when I was there; all the same ones, really - he didn't know who Miklos was, of course, but other than that - Sally, Nori, Murthy, Narasimhain, Ginzburg, Kottwitz[3], May... Oh, I guess I mentioned Kisin, and he wasn't there 20 years ago, was he?
One of the professors - Hochster - mentioned one of those Google problems while we were eating dinner. (His son works for Google.) You're given a balance, and 9 coins. The coins are of at most 2 different weights. (To simplify the problem, we chose to assume that if they were of different weights, these weights were Q-linearly independent.) Can you, in 3 weighings, determine whether or not all 9 coins are of the same weight? We (well, Nic and I and whoever else was there) suspect the answer is no. It's not too hard to do 2^n (or fewer) coins in n weighings, but is it sharp? Hochster apparently case-checked that 5 in 2 is impossible, but we weren't able to come up with any sort of argument for 9 in 3. Not that we worked on it for very long; and this is one of those Google problems, of course...
Also I caught someone talking about a countably infinite number of people wearing hats, and indeed it was this problem. This soon degenerated into people retelling hat puzzles and prisoners-forced-to-play-sadistic-games puzzles.
I'm sure many of you have seen these before, but now seems like a good a time as any to present some puzzles for those who haven't!
Puzzle #1: This actually didn't come up, but it's one Youlian likes to give to people, and it's a pretty simple one, so I'll state it here anyway as this is the place for it. You have n people, and n colors of hats. Each person is assigned a color of hat, independently of the others. They can strategize beforehand, but cannot communicate once the hats are on. Each guesses, simultaneously, the color of the hat he is wearing; how can they make a strategy that guarantees at least one of them gets it right?
Puzzle #2: The two-switch problem; I remember this one causing all sorts of confusion when I was a first-year at PROMYS. There are n prisoners. Once they are done strategizing, they will all be isolated and not be able to communicate in any way. The guards will pick a random prisoner from isolation and take him into a room with 2 switches, which both start in the down position. The prisoner must toggle one of these switches. Then the guards will again randomly pick a prisoner (could be same one), etc. At any point, the prisoner who has been picked can declare that all the prisoners have been in the room at least once; if he is correct, the prisoners win, if not, they lose. Devise a strategy that will with probability 1 eventually result in some prisoner declaring correctly, and will never result in declaring incorrectly.
Puzzle #3: There are n prisoners, and there is a room with n lockers (separate from where the prisoners are kept). The prisoners all have their wallets taken from them, and each wallet is placed in a different locker (randomly). Prisoners are led into the locker room one by one, no communication once they're done strategizing. Each prisoner may open up to half of the lockers in the room - they are attempting to find their own wallet. (Which they do not then take; all the prisoners will find the same contents in the lockers.) They may look inside a locker they've opened before opening another. If all the prisoners find their own wallet, they win, but even one does not, they lose.
Now, if they all just pick half the lockers randomly, that means they have a 1/2^n chance of winning (well, if n is even). Pretty bad. And if they all pick the same lockers, they have 0 chance of winning... so, it's clear that if you want to do better than 1/2^n, they'll have to coordinate somehow, but it's not even obvious that you can do better than 1/2^n. Well, in fact you can. The problem as posed by the guy here was, find a strategy that for large n, does better than, say, a 1/4 chance of winning. (Note that 1/4 was a pretty arbitrary number that's worse than how it'll do for large n, it's not a hint to precisely how well it'll do.)
Now the thing about this problem was that I had seen it before. Last year or maybe the year before, some guy had given a lecture at Chicago about... I forget what, but he had presented this problem during it (though not with prisoners and wallets, and he probably didn't pose it as "do better than 1/4"). Now the thing is - the solution to this problem is actually pretty complicated, but at that lecture Calvin got it very quickly, I have no idea how. And indeed when this came up now here, it took me quite a while to remember it...
-Harry
[0]Funny: never heard "prospie" used once; presumably that term is reserved for prospective undergrads. I guess the more proper term for us was "recruits", which we were sometimes called..
[3]Well, I never actually had Kottwitz for a class, but...
I briefly ran into ADan, he certainly wasn't expecting to see me. Also, I did not realize Brian Conrad teaches there, so when I saw him at first I was like "Why is Keith Conrad here?" before I realized it had to be Brian Conrad (which it was).
Also a prospective student[0] with me was Dave Putnins, back from BCA. I actually completely failed to recognize him. He's graduating in 3 years from Oxford (apparently it's usually only 3 years at English schools?). Funny thing, once it got to be nighttime, he kept making comments about how he was tired because he just flew in from England. But it wasn't until quite late that somebody heard this, listened to the voice he was saying it with, and responded, "Wait, you're not from England, you're from New Jersey!"
One of the professors I talked to, deBacker, was a student of Sally, and instead of finding much of anything out about Michigan we more or less just ended up comparing the Chicago professors when he was there vs. when I was there; all the same ones, really - he didn't know who Miklos was, of course, but other than that - Sally, Nori, Murthy, Narasimhain, Ginzburg, Kottwitz[3], May... Oh, I guess I mentioned Kisin, and he wasn't there 20 years ago, was he?
One of the professors - Hochster - mentioned one of those Google problems while we were eating dinner. (His son works for Google.) You're given a balance, and 9 coins. The coins are of at most 2 different weights. (To simplify the problem, we chose to assume that if they were of different weights, these weights were Q-linearly independent.) Can you, in 3 weighings, determine whether or not all 9 coins are of the same weight? We (well, Nic and I and whoever else was there) suspect the answer is no. It's not too hard to do 2^n (or fewer) coins in n weighings, but is it sharp? Hochster apparently case-checked that 5 in 2 is impossible, but we weren't able to come up with any sort of argument for 9 in 3. Not that we worked on it for very long; and this is one of those Google problems, of course...
Also I caught someone talking about a countably infinite number of people wearing hats, and indeed it was this problem. This soon degenerated into people retelling hat puzzles and prisoners-forced-to-play-sadistic-games puzzles.
I'm sure many of you have seen these before, but now seems like a good a time as any to present some puzzles for those who haven't!
Puzzle #1: This actually didn't come up, but it's one Youlian likes to give to people, and it's a pretty simple one, so I'll state it here anyway as this is the place for it. You have n people, and n colors of hats. Each person is assigned a color of hat, independently of the others. They can strategize beforehand, but cannot communicate once the hats are on. Each guesses, simultaneously, the color of the hat he is wearing; how can they make a strategy that guarantees at least one of them gets it right?
Puzzle #2: The two-switch problem; I remember this one causing all sorts of confusion when I was a first-year at PROMYS. There are n prisoners. Once they are done strategizing, they will all be isolated and not be able to communicate in any way. The guards will pick a random prisoner from isolation and take him into a room with 2 switches, which both start in the down position. The prisoner must toggle one of these switches. Then the guards will again randomly pick a prisoner (could be same one), etc. At any point, the prisoner who has been picked can declare that all the prisoners have been in the room at least once; if he is correct, the prisoners win, if not, they lose. Devise a strategy that will with probability 1 eventually result in some prisoner declaring correctly, and will never result in declaring incorrectly.
Puzzle #3: There are n prisoners, and there is a room with n lockers (separate from where the prisoners are kept). The prisoners all have their wallets taken from them, and each wallet is placed in a different locker (randomly). Prisoners are led into the locker room one by one, no communication once they're done strategizing. Each prisoner may open up to half of the lockers in the room - they are attempting to find their own wallet. (Which they do not then take; all the prisoners will find the same contents in the lockers.) They may look inside a locker they've opened before opening another. If all the prisoners find their own wallet, they win, but even one does not, they lose.
Now, if they all just pick half the lockers randomly, that means they have a 1/2^n chance of winning (well, if n is even). Pretty bad. And if they all pick the same lockers, they have 0 chance of winning... so, it's clear that if you want to do better than 1/2^n, they'll have to coordinate somehow, but it's not even obvious that you can do better than 1/2^n. Well, in fact you can. The problem as posed by the guy here was, find a strategy that for large n, does better than, say, a 1/4 chance of winning. (Note that 1/4 was a pretty arbitrary number that's worse than how it'll do for large n, it's not a hint to precisely how well it'll do.)
Now the thing about this problem was that I had seen it before. Last year or maybe the year before, some guy had given a lecture at Chicago about... I forget what, but he had presented this problem during it (though not with prisoners and wallets, and he probably didn't pose it as "do better than 1/4"). Now the thing is - the solution to this problem is actually pretty complicated, but at that lecture Calvin got it very quickly, I have no idea how. And indeed when this came up now here, it took me quite a while to remember it...
-Harry
[0]Funny: never heard "prospie" used once; presumably that term is reserved for prospective undergrads. I guess the more proper term for us was "recruits", which we were sometimes called..
[3]Well, I never actually had Kottwitz for a class, but...
" prisoners-forced-to-play-sadistic-games puzzles"
Date: 2009-03-22 09:26 pm (UTC)Regarding #3, I heard that before but with numbered cards rather than wallets. Getting a solution that always has a fixed chance of winning isn't really terribly difficult. A more difficult problem which I never solved is to work out what the optimal strategy is.
Re: " prisoners-forced-to-play-sadistic-games puzzles"
Date: 2009-03-22 09:26 pm (UTC)Re: " prisoners-forced-to-play-sadistic-games puzzles"
Date: 2009-03-22 10:15 pm (UTC)The strategy (assuming this is the same solution) certainly is optimal for the dumb cases of n=2 or 3, but... :P (Actually, that's presumably true even if you *aren't* thinking of the same solution.) But yeah, I have little idea how to tell whether it's optimal either.