Strange Creatures I

[araver]

During a cloudy night, on a far away distant barren planet in a far way galaxy, five creatures of five different species meet in a clearing near a lake. The planet is barren and hostile enough for all of them to survive better as a group. Four of them are herbivores, one of them is carnivorous (however it is not obvious which is which). A certain gas in the composition of the atmosphere makes all creatures develop only short-term memories and carnivorous creatures have developed to mimic their herbivore counterparts, so no herbivore species is able to recognize a carnivorous creature as being carnivorous until something (a scent, a sound, a series of movements) triggers an ancenstral memory. They are however sufficiently developed as species to follow (some form) of logical reasoning.

Each night, the carnivore may strike deadly to eat one of the herbivores. Each night, the herbivore's instinct makes them investigate (exactly one) element in their surroundings to discover a threat. Unfortunately they don't know what type they are, as they posess no long-term memory (more than 5 days).

* One of the species is notorious for being fearful of everything. We'll call them PARANOIDS because after they investigate another animal (even one of the same species) their brains marks the target as a carnivore threat (even if it is herbivore).

* The second species is notorious for being too trustful. We'll call them NAIVE because all their investigations lead to them trusting the targeted creature

* The third species is confused, to say the least, INSANE to be more precise. They always trust carnivores upon inspection and distrust herbivores (for no apparent reason).

* The fourth species is SANE. Their advanced senses make their results spot on. Always.

Each day, they can all share their results and discuss. Each day, all alive creatures must cast a vote for one of them to be sacrificed as a possible threat to the group. Votes can be changed once they are cast. If one of them reaches plurality (largest number of votes from total number of possible votes, not necessarily a majority of votes) at the end of the day he is sacrificed by the others and all will learn if they've sacrificed a herbivore or a carnivore before a new night begins.

1) Prove (or disprove) that there is a strategy that can be agreed beforehand (during first night) so that the herbivores win (win = no carnivore is alive in the group).

2) Prove (or disprove) that there is a strategy that can be agreed beforehand (during first night) so that the herbivores win if abstaining is allowed.

3) Prove (or disprove) that there is a strategy that can be agreed beforehand (during first night) so that the herbivores win if changing of votes is NOT allowed.

Or in a simpler setting:

5 creatures. 4 good / 1 bad. Each good creature can spy a single target each night, however with different results depending on their type. There are 4 types and there are no creatures of the same type among the 4 in our story.

*PARANOID spy - target is always seen as bad.

*NAIVE spy - target is always seen as good.

*INSANE spy - target is always seen the opposite of what it is

*SANE spy - target is always seen as what it is

And yes, the setting of the puzzle is largely borrowed from a social game humans play, that can factor in multiple other possibilities and is mostly nedeterministic.

But for the purposes of this puzzle, assume all creatures behave in a deterministic / logical / optimal manner. And if a strategy exists and proven using logical means, all creatures will follow it.

Edited January 19, 2013 by araver

[Molly Mae]

Nice to see you back in these parts, Araver. I have some observations from playing the game, but certainly no proof (or disproof) as to a perfect strategy. I think it largely depends on when the carnivore shares information.

EDIT: Prematurely hit submit. I'll wait to see what comes up.

Edited January 19, 2013 by Molly Mae

[k-man]

Hi Araver! Nice to see you again.

Can you clarify the sequence of events? I assume they agree on the strategy first, then they inspect each other, then a carnivore strikes and kills one herbivore. Then, when the day comes, with only 3 herbivores left they have only one chance of identifying a carnivore or they lose. Is this right?

[CaptainEd]

For that matter, does the carnivore get to take part in the deliberations--the decision on the proper strategy?

[araver]

Hi Araver! Nice to see you again.

Can you clarify the sequence of events? I assume they agree on the strategy first, then they inspect each other, then a carnivore strikes and kills one herbivore. Then, when the day comes, with only 3 herbivores left they have only one chance of identifying a carnivore or they lose. Is this right?

Hi! Indeed LTNS.

To clarify the sequence of events, abbreviating Day/Night, the following timeline is assumed strict:

during N1 - They can discuss / agree on strategy

end of N1 - Each herbivore can inspect one other and receive 1 result (according to it's species type)

end of N1 - carnivore strikes a chosen secret target, 1 herbivore dies

beginning of D1 - 3 herbivores and 1 carnivore left

during D1 - They can discuss and each of them (including the carnivore) get a vote which they MUST (or in case of (2) CAN) use on the other alive creatures.

end of D1 - If a plurality is reached, that creature is "sacrificed"

The rest of the timeline repeats itself, N2 follows, then D2, etc.with the same night/day events.

However I cannot answer your question other than using spoilers:

If they don't identify the carnivore and if a herbivore is sacrificed, then there are 2 herbivores and 1 carnivore left at the beginning of N2. In which case, they most probably lose.

[araver]

For that matter, does the carnivore get to take part in the deliberations--the decision on the proper strategy?

Indeed it does.

For all they know, all the other creatures look like herbivores so there is no point in trusting or not trusting any input in the deliberations.

P.S. Don't ask me how they know there is exactly one carnivore around. The backstory doesn't explain it. so take it as a more abstract MacGuffin

[araver]

Nice to see you back in these parts, Araver. I have some observations from playing the game, but certainly no proof (or disproof) as to a perfect strategy. I think it largely depends on when the carnivore shares information.

EDIT: Prematurely hit submit. I'll wait to see what comes up.

Nice to see you too

This 3-part puzzle is unlike the game in at least 3 ways (one of which may or may not be a red-herring).

But for the purposes of this puzzle (optimal adaptive strategy), one may assume the worst-case, in which the carnivore has ample time to prepare and share any kind of information. So if the strategy has a weak point, assume the adversary (carnivore) always finds it (and has time to find it).

[k-man]

However I cannot answer your question other than using spoilers:

If they don't identify the carnivore and if a herbivore is sacrificed, then there are 2 herbivores and 1 carnivore left at the beginning of N2. In which case, they most probably lose.

Not sure why you had to use a spoiler, as I find it very obvious (unless I'm missing something obvious ), but out of respect to you I will use spoiler too

You said "most probably", but isn't it a certainty? If on a D1 they sacrifice a herbivore, then there will be only 2 herbivores left for the N2. One of them will be killed that night leaving 1 herbivore against 1 carnivore for D2. Even if after sacrificing the herbivore on D1 they know who the carnivore is, they simply don't get a chance to kill him unless he votes against himself.

[araver]

However I cannot answer your question other than using spoilers:

If they don't identify the carnivore and if a herbivore is sacrificed, then there are 2 herbivores and 1 carnivore left at the beginning of N2. In which case, they most probably lose.

Not sure why you had to use a spoiler, as I find it very obvious (unless I'm missing something obvious ), but out of respect to you I will use spoiler too

You said "most probably", but isn't it a certainty? If on a D1 they sacrifice a herbivore, then there will be only 2 herbivores left for the N2. One of them will be killed that night leaving 1 herbivore against 1 carnivore for D2. Even if after sacrificing the herbivore on D1 they know who the carnivore is, they simply don't get a chance to kill him unless he votes against himself.

Let me rephrase it:

IF they don't identify the carnivore and IF a herbivore is sacrificed, then there are 2 herbivores and 1 carnivore left at the beginning of N2. In which case, they most probably definitely lose.

[Molly Mae]

Given these constraints, the carnivore should win in almost all (3/4) cases. The herbivores will never have enough information by the time the carnivore can kill two of them.

N1 - an arbitrary herbivore is killed and each herbivore eliminates two possibilities of his species (no information is gained about other herbivores)

D1 - all creatures must vote. As there are four creatures left, all three herbivores must vote for the carnivore in order to kill him.* If the vote ever comes down to a 2-2 split (and the carnivore is not part of that split), he can change his vote to create a 3v1 vote, and he wins. All other cases are dependent on when the vote "ends" and the votes are actually tallied (assumption: after everyone votes at least once and a plurality is reached). If this phase cannot end without a creature dying, the carnivore has an extreme advantage.

N2 - the herbivores now have a chance to determine what their species is, but it is too late. The carnivore will eliminate another herbivore.

D2 - The last herbivore will know who the carnivore is, but will never be able to eliminate him since the vote will be 1v1 and no plurality will ever be reached.

*Note: This creates a situation where a re-evaluation might even change the minds of those herbivores.

[araver]

Inline

Given these constraints, the carnivore should win in almost all (3/4) cases. The herbivores will never have enough information by the time the carnivore can kill two of them.

N1 - an arbitrary herbivore is killed and each herbivore eliminates two possibilities of his species (no information is gained about other herbivores)

Correct.

D1 - all creatures must vote. As there are four creatures left, all three herbivores must vote for the carnivore in order to kill him.* If the vote ever comes down to a 2-2 split (and the carnivore is not part of that split), he can change his vote to create a 3v1 vote, and he wins.

If changing is allowed (1+2 of the puzzle) and if all creatures must vote ... maybe.

If changing is not allowed (3), then it depends on the timing of the votes.

All other cases are dependent on when the vote "ends" and the votes are actually tallied (assumption: after everyone votes at least once and a plurality is reached).

If changing is allowed (1+2 of the puzzle), then voting ends after a given time (let's call that moment twilight's end ).

If changing is not allowed (3) / all votes are final, then voting can effectively end after the last vote is placed.

If this phase cannot end without a creature dying, the carnivore has an extreme advantage.

Theoretically, it can end without a creature dying.

For (1), (3): 4 vs 0, 3 vs 1 or 2 vs 1 vs 1 are plurality votes, 1 vs 1 vs 1 vs 1 is the case where no one dies.

For (2), it's more complicated.

N2 - the herbivores now have a chance to determine what their species is, but it is too late. The carnivore will eliminate another herbivore.

D2 - The last herbivore will know who the carnivore is, but will never be able to eliminate him since the vote will be 1v1 and no plurality will ever be reached.

*Note: This creates a situation where a re-evaluation might even change the minds of those herbivores.

Edited January 29, 2013 by araver