|
So day 4!
Previous day's puzzle was first solved by Abydos1 or Hamster1800. Abydos1 has very good intuition but Hamster1800's answer is more precise.
+ Show Spoiler [solution] +
define a function f to be the difference in heights of 2 opposite points, x and x+pi. f(x) = height(x) - height(x+pi) where x is an angle, range from 0 to 2pi.
f(0) can either be >0, <0, or = 0.
If f(0)=0, then we're done.
The case of f(0)>0 and f(0)<0 is symmetrical, so we'll suppose f(0)>0.
f(0)>0 means height(0)-height(pi)>0.
However, since height(0)=height(2pi) because the track is continuous, we'll also have
height(2pi)-height(pi)>0 by substitution.
Rearranging we find that f(pi)=height(pi)-height(2pi)<0
Therefore we have a function f, moving from f(0)>0 to f(pi)<0, then at some point between 0 and pi, say c, f(c)=0.
That is to say, height(c)=height(c+pi), for some c, and that those 2 point are the opposite point with same height.
Today's puzzle is this:
You have n prisoners, and a warden who has a wardrobe. In this wardrobe there are hats of n colors, with many hats for each color(>n).
For example, if there are 3 prisoners, there will be 3 different colors of hats, say red hats, green hats, and blue hats, with more than 3 each, Say 10 red hats, 4 green hats, and 6 blue hats, for instance.
The game:
-Warden will put one hat(any color the warden wishes) on each of a prisoner's head, a prisoner cannot see the color of his own hat, but can see everyone else's hats.
-The prisoner cannot communicate to each other when the game starts.
-The prisoner will write down on a piece of paper what color hat he thinks he himself is wearing.
-If AT LEAST 1 prisoner guesses his own hat's color correctly, they all get to be free.
Your job:
Devise a strategy for the prisoners before the game starts, so at least 1 person would guess his own hat color correctly.
Extra information:
-Warden will also know the strategy as well, and he will try to put hats in a certain way if your strategy can fail.
Clarifications:
On April 30 2009 19:49 MasterReY wrote:
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?
No, but they do know it is greater than n, and they cannot see the wardrobe before/after.
On April 30 2009 20:03 Nytefish wrote:
Do they know what colours are possible?
On April 30 2009 20:03 Zona wrote:
Do the prisoners know before what the specific colors are?
-Yes. They will know the n possible colours beforehand.
Again, put answers in spoiler tags, and clarification will be given as needed.
GL HF!
|
Spenguin
Australia3316 Posts
|
so anyone can get an any coloured hat, and they can't communicate in any way
This is HARD.
|
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?
|
On April 30 2009 19:49 MasterReY wrote:
do prisoners know how many hats of a certain color are in the wardrobe before/after warden puts the hats on the prisoners?
No, but they do know it is greater than n, and they cannot see the wardrobe before/after.
|
Do they know what colours are possible?
|
Do the prisoners know before what the specific colors are?
|
This is how they get released.
+ Show Spoiler +All the prisoners take their pencil/pens and attack the warden all at once.
P.S. Saving this post for when I figure out the answer
|
On April 30 2009 20:03 Nytefish wrote:
Do they know what colours are possible?
On April 30 2009 20:03 Zona wrote:
Do the prisoners know before what the specific colors are?
Yes. They will know the n possible colours beforehand.
|
|
|
i've solved this kind of problem twice before already and still forget how to do it 
|
|
|
Why am I still up...
+ Show Spoiler +n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.
|
+ Show Spoiler +There are n colors. Assign a different number from 1 to n for each of the colors. Take the sum of all the hats (numbers) on all of the n prisoners, and mod n this sum. This sum mod n is a number from 0 to n-1.
Each prison cannot see their own hat, of course, so they do not know what the sum mod n is. However, if each prison guesses a different answer for the sum mod n, one of them will be correct. And if you have the correct sum mod n then it is possible to figure out your own hat color.
|
But you only know the colour of the hats, not how many of each you have.
|
One guy writes YOUR HAT IS N COLOR on his paper and shows it to the prisoner he just wrote about.
|
On April 30 2009 20:23 raiame wrote:Why am I still up... + Show Spoiler +n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.
but they can't communicate at all
|
+ Show Spoiler +Each colour will be assigned a number from 1 to n. Every prisioner will write whatever colour onto the paper except for the two who are chosen last. The second last person will take 5X seconds to write down on his piece of paper, where X is the number that was assigned to the colour on the last prisioner's hat. The last prisioner will count how long the second person takes, and will then know which colour hat he is wearing.
|
On April 30 2009 20:35 freelander wrote:Show nested quote +On April 30 2009 20:23 raiame wrote:Why am I still up... + Show Spoiler +n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from. but they can't communicate at all
If I'm not mistaken they can communicate before the game starts.
Also
On April 30 2009 20:50 Rhaegar99 wrote:+ Show Spoiler +Each colour will be assigned a number from 1 to n. Every prisioner will write whatever colour onto the paper except for the two who are chosen last. The second last person will take 5X seconds to write down on his piece of paper, where X is the number that was assigned to the colour on the last prisioner's hat. The last prisioner will count how long the second person takes, and will then know which colour hat he is wearing.
LOL
|
On April 30 2009 20:23 raiame wrote:Why am I still up... + Show Spoiler +n colors, assign each color a different number from 1 to n. also, assign each person a number from 1 to n. have each person add up the values of the colors of each hat he sees, and we'll call this number s(k), where k is the number of the prisoner. Have prisoner k say the color corresponding to k - s(k) (mod n). This works because for each person, s(k) plus the color of their own hat is the same total sum, so subtracting s(k) from this total sum gives your own hat. You make sure that each possible total sum (mod n) is accounted for by assigning each prisoner a different number to subtract from.
I bet the warden didn't see that one coming. Sounds like you've been in this situation before prisoner raiame.
|
|
|
|
|
|
EPT
