Brainteaser: General's colours

[chmith]

Hi there,

A general summons 50 soldiers to his tent. He points out two medals on the wall, both of them with one silver side and one gold side. He tells them that he will summon one soldier every day to come and switch one of the medals around, so that the other side faces into the tent. The general may choose which soldier as he pleases and may choose the same soldier multiple times. The soldier gets to choose which medal to flip around. He then tells the soldiers that if anyone of them can, at any point in time, tell him that all 50 soldiers have been called into the tent, and be right, all of them will get paid for life without working anything. If the soldier is wrong in his statement, they will all have to work one year with no salary. The soldiers are given 10 minutes to discuss and may not communicate after that until the task is completed.

What should their strategy be?

 

[davee123]

If it's what I'm thinking it is, it'll take them over 7 years average case... If he called them in every hour, then you'd be down to about 111 days average (assuming the general stays awake every hour).

Admittedly, I did hear some interesting solutions that allowed for faster average cases, although I don't think I ever heard what the optimal balance was in those situations.

DaveE

 

[chmith]

If it's what I'm thinking it is, it'll take them over 7 years average case... If he called them in every hour, then you'd be down to about 111 days average (assuming the general stays awake every hour).

Admittedly, I did hear some interesting solutions that allowed for faster average cases, although I don't think I ever heard what the optimal balance was in those situations.

DaveE

Hi DaveE,
I thought of the average solution as well, but unfortunately it's not the right answer. The soldiers are not chosen randomly, and their downside is quite large so they will want to know FOR SURE before they are guessing. If the general is close to rational he will only use 49 of the soldiers so that he never runs the risk. The strategy must therefore be to work as normal but keep track IN CASE the general is stupid enough to select all 50 soldiers at some point. An example of a solution would be for the soldiers to commit suicide after the first time they have been in hte tent. This would mean that the guy called on the 50th day can safely say that all of them have been in there. Unfortunately there are other reasons why this is not a valid strategy.. :)

 

[fleem]

Hi there,

A general summons 50 soldiers to his tent. He points out two medals on the wall, both of them with one silver side and one gold side. He tells them that he will summon one soldier every day to come and switch one of the medals around, so that the other side faces into the tent. The general may choose which soldier as he pleases and may choose the same soldier multiple times. The soldier gets to choose which medal to flip around. He then tells the soldiers that if anyone of them can, at any point in time, tell him that all 50 soldiers have been called into the tent, and be right, all of them will get paid for life without working anything. If the soldier is wrong in his statement, they will all have to work one year with no salary. The soldiers are given 10 minutes to discuss and may not communicate after that until the task is completed.

What should their strategy be?

Quit. Because the general is a kook, and thus more likely to put them in harms way without good reason.

... unless they believe there is a chance the general may choose to call all of them out of the goodness of his heart. But that is unlikely because one of the requirements of being a general is not to waste tons of state money. Also there is the question of whether the general could deliver.

 

[mXSCNT]

The soldiers can communicate with 1 bit of information--if s=silver, g=gold, then a soldier can decide to send either the message sg/gg, or the message gs/ss. Call the first message "0" and the second message "1." You can convince yourself that it is always possible to choose a 0 or a 1, no matter how the medals are currently facing.

One way, that would prevent a mistake but might take a long time, is to have one of the soldiers be a "designated counter." The first soldier called up puts the medals in state 0. Thereafter, if a soldier sees the state is 0, he sets it to 1, unless he is the counter or has already changed the state from 0 to 1--in which case he keeps it at 0. If a soldier sees the state is 1, he keeps it 1, unless he is the counter, in which case he switches it to 0. The counter counts the number of times he has switched the state from 1 to 0. When that number reaches 49, he declares victory.

 

[davee123]

I thought of the average solution as well, but unfortunately it's not the right answer.

That isn't an issue-- the normal solution (IE the "100 Prisoners" problem) will be absolutely 100% be guaranteed to solve the problem. It'll just take 7 years average case, assuming that the general picks randomly. The general could (for all intents and purposes) just keep picking the same guy every day, and he'd be guaranteed never to have to worry about it.

The solution that mXSCNT posted is the pretty typical solution here-- IE, instead of a light switch, you flip a medal. Check the forum history to for the 100 prisoners problem (it's been listed here several times, actually), and you'll see an interesting take on it that speeds up the average case (again, assuming a random distribution of people picked). But IIRC, nobody was able to figure out what the optimal distribution was in that case (it's like having multiple tiers of counters, and the question of optimality is how many tiers should you have, and how many you should allot at each tier).

An example of a solution would be for the soldiers to commit suicide after the first time they have been in hte tent. This would mean that the guy called on the 50th day can safely say that all of them have been in there. Unfortunately there are other reasons why this is not a valid strategy.. :)

Actually, your problem leaves out one phenomenally tremendous stipulation, which is that they aren't allowed to communicate with each other about the situation. Hence, as stated, they should just all congregate every night and ask each other whether they've all been to the tent or not. But WITH the stipulation, then committing suicide isn't a viable option because that could be used as a form of communication (albeit a bad one).

DaveE

 

[chmith]

The soldiers can communicate with 1 bit of information--if s=silver, g=gold, then a soldier can decide to send either the message sg/gg, or the message gs/ss. Call the first message "0" and the second message "1." You can convince yourself that it is always possible to choose a 0 or a 1, no matter how the medals are currently facing.

One way, that would prevent a mistake but might take a long time, is to have one of the soldiers be a "designated counter." The first soldier called up puts the medals in state 0. Thereafter, if a soldier sees the state is 0, he sets it to 1, unless he is the counter or has already changed the state from 0 to 1--in which case he keeps it at 0. If a soldier sees the state is 1, he keeps it 1, unless he is the counter, in which case he switches it to 0. The counter counts the number of times he has switched the state from 1 to 0. When that number reaches 49, he declares victory.

Brilliant solution! Just trying to figure out if there is any way they might make it more efficient?

 

[Fenn]

I think the 50 soldiers should overthrow the general. It is obvious that the general cares more for tormenting his troops than fulfilling his duty.

If anyone asks, it can turn into a re-enactment of Weekend at Bernie's, where the general is assumed alive because of an elaborate concoction of strings and pulleys making it look like he's drinking a beer, having a cigarette, etc.

 

[chmith]

That isn't an issue-- the normal solution (IE the "100 Prisoners" problem) will be absolutely 100% be guaranteed to solve the problem. It'll just take 7 years average case, assuming that the general picks randomly. The general could (for all intents and purposes) just keep picking the same guy every day, and he'd be guaranteed never to have to worry about it.

The solution that mXSCNT posted is the pretty typical solution here-- IE, instead of a light switch, you flip a medal. Check the forum history to for the 100 prisoners problem (it's been listed here several times, actually), and you'll see an interesting take on it that speeds up the average case (again, assuming a random distribution of people picked). But IIRC, nobody was able to figure out what the optimal distribution was in that case (it's like having multiple tiers of counters, and the question of optimality is how many tiers should you have, and how many you should allot at each tier).



Actually, your problem leaves out one phenomenally tremendous stipulation, which is that they aren't allowed to communicate with each other about the situation. Hence, as stated, they should just all congregate every night and ask each other whether they've all been to the tent or not. But WITH the stipulation, then committing suicide isn't a viable option because that could be used as a form of communication (albeit a bad one).

DaveE

Hi Dave, thanks, will check out the 100 prisoners problem. I did actually state that they are not allowed to communicate though, and if you think that suicide can be considered a type of communication, so is flipping the medals in a certain pattern.

 

[junglebeast]

Hi there,

A general summons 50 soldiers to his tent. He points out two medals on the wall, both of them with one silver side and one gold side. He tells them that he will summon one soldier every day to come and switch one of the medals around, so that the other side faces into the tent. The general may choose which soldier as he pleases and may choose the same soldier multiple times. The soldier gets to choose which medal to flip around. He then tells the soldiers that if anyone of them can, at any point in time, tell him that all 50 soldiers have been called into the tent, and be right, all of them will get paid for life without working anything. If the soldier is wrong in his statement, they will all have to work one year with no salary. The soldiers are given 10 minutes to discuss and may not communicate after that until the task is completed.

What should their strategy be?

Every time a solider is called into the tent, upon returning he enters his name into a list. When the list has 50 names one of them goes and claims the prize.

 

[mXSCNT]

Brilliant solution! Just trying to figure out if there is any way they might make it more efficient?

One possible way to make it more efficient is to use 2 counters. Each counter counts to only 24. If he reaches his total, he behaves like an ordinary soldier again. This state of affairs continues for n days, where n is a number chosen so that it is very likely both counters will have reached their totals after n days. (for example, n=5000 might be a reasonable choice, just to make a guess).

After the n days have passed, a "consulting period" begins, lasting d days (d=200 might be reasonable). The first soldier called up in the consulting period sets the medals to 0. Every soldier after that keeps the medals in the state they are already in, unless that soldier is one of the counters, AND that counter has reached his total of 24, in which case he sets the medals to 1 if it was 0. If the counter has reached his total and the medals are already 1 (indicating the other counter also reaches his total), the counter declares victory.

If the consulting period ends without victory declared, you can repeat the process (with the counters remembering their totals from the previous time).

The advantage of this method is that you have 2 people counting in the beginning instead of just 1, which can speed things up. Just how fast depends on n and d.

You could even use more than 2 counters if you wanted--that might speed things up even more. But you would have to use more than one consulting period to be sure every counter got his total. You could potentially use a fairly complex strategy to try to synchronize all the counters--there isn't one clear path.

--> Actually there is a bug in the 2 counter technique. Suppose that on the nth day, the state was still 1 (a soldier signalled but never got counted). According to my earlier statement, that signal would just "vanish" and the soldiers would never finish. I can think of a way to resolve this bug.

 

[mXSCNT]

So here is a general class of techniques for solving this problem.

Each soldier maintains a count, initially 1 for each soldier.

Time is divided into pre-agreed intervals. In each interval, a message (a state of 1) carries a certain count.

At each day except the last day of an interval, a soldier may do one of the following:
-- if the state of the medals is 0, and the soldier's count is at least as large as the interval count, the soldier may (if he chooses) "send" a signal. He changes the state to 1, and reduces his count by the interval count.
-- if the state is 1, the soldier may (if he chooses) "pick up" the signal. He sets the signal to 0, and then increases his count by the interval count.
-- otherwise, the soldier leaves the medals in their previous state
-- if the soldier's count is 50, he declares victory

On the last day of an interval, if the state is 1, the soldier MUST pick up the signal (increase his count by the interval count, and set the state to 0). This is to prevent the signal from being "lost" (which would be a disaster).

For example: in the solution with just 1 counter, there is just 1 interval, and the interval count is 1. Every soldier except the counter always chooses to send a signal whenever possible, and never picks a signal up. The counter always chooses to pick up a signal whenever possible, and never sends a signal.

The solution with 2 counters I gave earlier can also be put in this framework.

The question is, what is the best technique in this framework?

 

[davee123]

I did actually state that they are not allowed to communicate though, and if you think that suicide can be considered a type of communication, so is flipping the medals in a certain pattern.

Ooops, I guess I missed that bit at the tail end, sorry about that! Here's the link to the existing thread, check out pig's solution on the first page:

https://www.physicsforums.com/showthread.php?t=30021

His solution worked much faster for the average case, although optimal speed wasn't really determined.

DaveE

 

[Vectus]

I assume the medals must be hanging from a string or a rope such that they can be 'flipped' easily. Such is not stated, but is logical, and would mean that the 50th soldier could know on his first trip that he is the 50th soldier to be summoned because more information can be stored and conveyed:

The soldiers predetermine a specific number based on how many knots the rope can support by flipping a medal in one direction successively as many times as is possible without it becoming too difficult to discern the number of times it has been flipped.

If it is a soldier's first time entering the tent, they should flip the first coin to the right one time, such that an extra knot is added in the string supporting the medal. If not, take the second coin off of the wall and flip it so that the state of the strings is not changed.

If a soldier visits the tent for the first time and the first medal's string has the predetermined number of knots in it, he should take the first medal off of the wall and flip it around so that the other side is showing, thus indicating that the predetermined number has been reached and the current count is p+1.

Every soldier who visits for the first time and sees the indication should then flip the first medal one time to the left, undoing one knot, unless only one knot is left. If one knot is left, the soldier should then turn the second medal once to the right (doesn't matter which way it's facing, you're still turning it counter-clockwise when viewed from above).This will take forever to continue typing out like this, so I'll use numbers instead. I hope I got the general pattern across.---------------------------------------------
---------------------------------------------p = predetermined number
---------------------------------------------

0 / 1 <- turns first to the right until predetermined number is reached
0 / 2
...
0 / p
0 / (i)p <- indication, swaps first medal around so other side is showing indicating count is p+1
0 / (i)p-1
0 / (i)p-2
...
0 / (i)0
1 / (i)0 <- indication, adds one to the second medal indicating count is 2p+2
2 / (i)0
...
p / (i)0
p / (i)-1 <- indication, once second medal reaches predetermined number, turns the first to the left indicating count is 3p+2
p / (i)-2
...
p / (i)-p
p-1 / (i)-p <- indication, once first has been turned to the left the predetermined number of times, the second is turned once to the left to reduce count by one, indicating count is currently 4p+2

---------------------------------------------
---------------------------------------------

This pattern continues until the count is 50. As long as p is 2 or greater, there should be no issue given a clever enough system as there are exactly 50 possible unique combinations using two bits, both storing positive, negative, and i 1-2 and the second storing one byte of communicative information with the i-ness of the number (no information can be stored with i# in the second bit). Since no information is conveyed initially with the combination 0/0, you start with 0/1. When it finally rolls over to 0/0, the soldier is the 50th and can declare such.

If p is much greater than 2 (I was able to get 27 on a string about the length of one that would be used to carry a medal around your neck), this task is completely trivial.Of course, this fails if the medals are hanging on a nail or its a really thick or really short string (p=0, 1). :(

 

[i.neu]

and may not communicate after that until the task is completed.

It is absolutely impossible to solve this problem if communication is not allowed.

 

[phlegmy]

they use the medals as a binary counter

0= silver silver
1=silver gold
2=gold silver
3= gold gold

they nominate a COUNTER, he is only one who resets the medals to 0

each soldier changes the medals ONLY ONCE!

if a solder is called and the medals are at 3, he waits for his next calling before incrementing.

when the COUNTER is called he knows how many soldiers have switched the medals (up to 3)
and he resets the medals to zero, keeping a tally.

when his tally reaches 49 he knows for sure that the other 49 soldiers have switched the medals.

i believe this should take about 848 days
this estimation is based on the average of 250 simulations of the stategy, although i need a better random number generator!
personally i'd rather work for free for a year than not be able to communicate

 

[Alsdfj12]

The general doesn't pay soldiers: being a soldier is not a job, therefore, no matter what, no one gets paid. If they are right, then life will go on, because its not a job, therefore, you don't "work," you just train, and if they aren't, life will go on as normal.

 

[crimsonreaper]

this is not a mathematical qeustion it is a logistics case if he can call the same soldier in as many times as he wants he could keep this going on for eternity and they cannot talk to each other about who was called so the general could leave one soldier out the whole time and maybe call him into talk about his work in the army making the other soldiers think that he has switched one of the medalion's around so this general would be a crook because it would be very easy to get away with not paying them for those years that are mentioned

 

[crimsonreaper]

The general doesn't pay soldiers: being a soldier is not a job, therefore, no matter what, no one gets paid. If they are right, then life will go on, because its not a job, therefore, you don't "work," you just train, and if they aren't, life will go on as normal.

evan in 800 BC soldiers have bin given pay for their work with the army m8 unless of course you are talking about slave fighters but these are soldiers so thus they are getting money look at today and now they pay soldiers as they have for a very long time

 

[crimsonreaper]

I assume the medals must be hanging from a string or a rope such that they can be 'flipped' easily. Such is not stated, but is logical, and would mean that the 50th soldier could know on his first trip that he is the 50th soldier to be summoned because more information can be stored and conveyed

there is no way it would be on a rope because after it was wound it would flip back because of the build up of energy caused by the twisting of the rope so if anything it would be on a stand of some sort so there would be no trace of how many times it was flipped besides he can call in the same soldier as many times as he wants so they could be flipped 1mil times