« previous next »
Pages: [1]   Go Down

Author Topic: Red and Blue hats  (Read 6472 times)

0 Members and 1 Guest are viewing this topic.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Red and Blue hats
« on: July 21, 2012, 12:49:42 am »
So a large village of people lives by a forest that is terrorized by a goblin.  Occasionally when a large group of villagers go out to hunt, the goblin takes kidnaps them and plays a cruel game with them.  The goblin first forces the villagers to stand in a single file line with each villager facing the one in front of him, and then places either a red or a blue hat on each villager such that they do not know what color hat they have on.  If any villagers move or make any sort of signal, the goblin kills all of the villagers immediately.  The goblin then starts from the back of the line (starting with the villager with nobody behind him that is) and asks them which color hat they are wearing.  The villagers must either answer red or blue, and any variation or movement once again gets all the villagers killed.  If the villager is wrong, he gets his head bitten off, and if he is correct, he is permitted to live, but must stand in his location without moving until the goblin is finished.  After the goblin is finished asking each villager, all the ones still alive are permitted to leave safely.

The villagers (or at least the survivors) over time have come to learn the goblins game very well, and so set out to determine if there is a best strategy they can use to ensure the highest survival rate on average.  They keep in mind that all villagers can hear the responses of all villagers before them, and a villager will know when a fellow villager answers incorrectly based on the sound of their head being eaten.  All villagers can also see the hat color of all villagers in front of them.

So the question stands, if all of the villagers can come up with a strategy beforehand, what would the most optimal strategy be?
Logged
+4/-0 karm for this message

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: Red and Blue hats
« Reply #1 on: July 21, 2012, 02:57:29 am »
PMed my answer :)
I can save at least N-2 villagers (considering N>2)
Logged
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Red and Blue hats
« Reply #2 on: July 21, 2012, 05:07:31 am »
You can save N-1 villagers with just a slight modification of your logic :)
Logged

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Red and Blue hats
« Reply #3 on: July 21, 2012, 06:41:07 am »
Well, if any of the villagers in the line have ADHD, they're all screwed :P jk

Is there an even number of red and blue hats or are the numbers arbitrary?
Logged

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...

Offline cyanophycean314

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 363
  • Rating: +43/-1
  • It's You!
    • View Profile
Re: Red and Blue hats
« Reply #4 on: July 21, 2012, 10:02:21 am »
Hmmm.... maybe this has something to do with sacrificing to let other people know in front of you what they're wearing?  ???
Logged

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: Red and Blue hats
« Reply #5 on: July 21, 2012, 10:07:56 am »
Quote from: Builderboy on July 21, 2012, 05:07:31 am
You can save N-1 villagers with just a slight modification of your logic :)
PMed you my update :P
Logged
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Red and Blue hats
« Reply #6 on: July 21, 2012, 03:39:23 pm »
Perhaps I'm misunderstanding the rules. But I'm fairly certain I can save all but the first villager.

Spoiler For Spoiler:
If the person in front of you has a red hat, you respond with a high pitch voice.

If the person in front of you has a blue hat, you respond with a low pitch voice.
Logged
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline parserp

  • Hero Extraordinaire
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1455
  • Rating: +88/-7
  • The King Has Returned
    • View Profile
Re: Red and Blue hats
« Reply #7 on: July 21, 2012, 03:44:12 pm »
But are they asking from the front person to the back person? If so, thep's answer wouldn't work. :-\

EDIT: didn't read the whole post :P Looks like thep's answer saves all but .5 of the first person. (He has a 50% chance of guessing what hat he has on) :P
« Last Edit: July 21, 2012, 03:46:30 pm by parserp »
Logged

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Red and Blue hats
« Reply #8 on: July 21, 2012, 04:03:23 pm »
Mine would work, but I'm fairly certain it's cheating.
Logged
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Red and Blue hats
« Reply #9 on: July 21, 2012, 04:31:11 pm »
Lol yeah that is cheating
Logged

Offline Scipi

  • Omni Kitten Meow~ =^ω^=
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1547
  • Rating: +192/-3
  • Meow :3
    • View Profile
    • ScipiSoftware
Re: Red and Blue hats
« Reply #10 on: July 22, 2012, 10:41:57 am »
Sent in my answer. It assumes the villagers know how many red and blue hats there are though :P
Logged

Imma Cat! =^_^= :3 (It's an emoticon now!)
Spoiler For Things I find interesting:
Spoiler For AI Programming:
Spoiler For Shameless advertising:

Spoiler For OldSig:





Spoiler For IMPORTANT NEWS!:
Late last night, Quebec was invaded by a group calling themselves, "Omnimaga". Not much is known about these mysterious people except that they all carried calculators of some kind and they all seemed to converge on one house in particular. Experts estimate that the combined power of their fabled calculators is greater than all the worlds super computers put together. The group seems to be holding out in the home of a certain DJ_O, who the Omnimagians claim to be their founder. Such power has put the world at a standstill with everyone waiting to see what the Omnimagians will do...

Wait... This just in, the Omnimagians have sent the UN a list of demands that must be met or else the world will be "submitted to the wrath of Netham45's Lobster Army". Such demands include >9001 crates of peanuts, sacrificial blue lobsters, and a wide assortment of cherry flavored items. With such computing power stored in the hands of such people, we can only hope these demands are met.

In the wake of these events, we can only ask, Why? Why do these people make these demands, what caused them to gather, and what are their future plans...
Pages: [1]   Go Up
« previous next »