A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Posts: 5
Joined: Sun Oct 21, 2018 11:06 am UTC


Postby Jayraj » Fri Oct 26, 2018 5:50 pm UTC

You are parched and famished, but manage to reach the outpost to find a few chicken scurrying about and a container full of canisters.
You assume the canisters contain juice as read from the diary at the military camp, however you also find a label on the floor, presumably detached from one canister.
The label says 'Strychnine solution', which you know is a deadly poison.
Further reading shows that effects of the poison become visible within a few hours on small animals and at most a day on humans.
You go through all the canisters to find there are 101, but you are unable to distinguish which one of them contains the poison.

Some of your companions have managed to capture a number of chicken in hopes of eating them.
However your thirst is your first priority and thus you are willing to sacrifice the chicken to identify the poisoned canister.
Your companions are already on the verge of passing out from thirst and cannot wait more than a few hours.

Can you identify the poisoned canister and the minimum number of chicken needed in this sacrifice?

There is no other source of drinkable liquid that you can find, and food looks to be very scarce.

Posts: 143
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Sacrifice

Postby DavidSh » Sat Oct 27, 2018 3:30 pm UTC

What seems to me to be the natural solution is
Number the 101 canisters 0 through 100, and label them in binary: 0000000 through 1100100.

Then take 7 chickens, label them 1 through 7. For each bit K, K=1..7, mix a potentially detectable dose from the approximately 50 canisters for which bit K is set to 1, and feed it to chicken K. Observe which chickens are affected by the poison. Set the bits for the affected chickens to 1, and the bits for the unaffected chickens to 0, and read off the number of the poisonous canister.

I think you could do it with fewer chickens only if you can make more than a single yes-no observation per chicken. Maybe you could distinguish between a chicken with a single dose and a chicken with a triple dose. But you can't distinguish between 101 states with fewer than 7 yes-no observations.

Posts: 29
Joined: Fri Feb 05, 2016 5:42 pm UTC

Re: Sacrifice

Postby Tirear » Mon Oct 29, 2018 3:49 pm UTC

Smartass solution:
We only need two chickens. Chicken one takes a sip from half the canisters. If it show symptoms, the other half are known to be safe which should buy time for the other chicken to test the unsafe canisters one at a time. If it doesn't show symptoms, those canisters are known to be safe, which should buy time for the two chickens to test the remainder 1 each at a time, with one of the chickens surviving to be used as food.

Regular solution:
DavidSh wrote:What seems to me to be the natural solution is

The one change I would suggest is to relabel #63 (0111111) and #95 (1011111) as #101 (1100101) and #102 (1100110). This helps with the secondary objective by guaranteeing that at least two chickens remain untainted. You could go even further and use all 4 or less chicken solutions + two 5 chicken solutions. If you are stuck on the assumption of labelling them in numerical order this seems like a bothersome task, but if you subdivide by number of chickens used and label each set in decreasing order it should happen fairly smoothly.

Posts: 4
Joined: Fri Jul 08, 2011 8:40 pm UTC

Re: Sacrifice

Postby bjazz » Mon Nov 05, 2018 3:04 pm UTC

Go back to your smartass solution for a second - there's more to be done there to get a solution with at most 4 chicken risked, and if you're lucky you lose none:
Separate the cans into three groups 34/34/33 cans each. Give sips from group 1 to chicken #1, and from group 2 to chicken #2. Don't give any chicken any from group 3. If one chicken dies, then you've narrowed it down to at most 34 cans. If no chicken dies, then you've narrowed it down to 33 cans and no chicken sacrifice!

Keep going this way and you only have to risk at most 4 chickens, and if you're lucky you don't lose any.
The next round is groups of 12/12/11, then a third round of 4/4/4.

Once you're down to 4 cans, do 1/1/2. If no chicken dies, then just give 1 chicken 1 of the remaining 2.

So there you go - at most 4 chickens risked, and possible to sort with no chickens lost.

Posts: 127
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: Sacrifice

Postby Yat » Tue Nov 06, 2018 9:48 am UTC

bjazz wrote:Go back to your smartass solution for a second - there's more to be done there to get a solution with at most 4 chicken risked, and if you're lucky you lose none

But then, we can do better, with the "break the game" solution:
Take one chicken, make it sip from the first canister. If it dies, you can feast on all the remaining canisters, if it lives you can ration the first canister, rinse and repeat. Same as with your solution, there is 1/101 chances that all chickens live, but in all other cases I only have one dead chicken on my hands.
Ok, one canister may not be enough to calm the thirst emergency until the next canister has been tested, but in that case, you can just make the chicken taste exactly the number of canisters required at each step, switching back to one when there is no emergency anymore. If the poisonous canister is identified as being part of a group, then you can use a second chicken to parse this smaller group and end up having a maximum number of chicken casualties to 2.
But if, as the puzzle seems to be implying without stating it explicitly, you absolutely need all 100 non poisonous canisters for when the poison kicks in on any chicken that tested it, then you are stuck with Tirear's regular solution.

User avatar
Posts: 325
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: Sacrifice

Postby ThirdParty » Tue Nov 13, 2018 1:45 am UTC

Assuming our goals are:
1. Identify all of the safe cans in the shortest possible time. (i.e. We're in "Regular Solution" territory rather than "Smartass Solution" territory.)
2. Kill as few chickens as possible while still achieving objective 1.

Then the optimal solution is:
Use all N chickens that are available. Label them "1" thru "N". Label the cans sequentially in base N+1, skipping any numerals which have repeated or non-ascending digits. (For example, if there are 9 chickens available, the cans should be labeled "1", "2", ..., "9", "12", "13", ..., "19", "23", ..., "29", "34", "35", ..., "69", "78", "79", "89", "123", "124", ..., "129", "134", "135", ..., "179", "189", "234", ..., "289", "345", ..., "357".) Feed a sample of each can to any chicken whose number appears as one of the digits in the can's number.

If you know exactly how long it takes a chicken to die of the relevant dose of strychnine, you can also label one can "0" and set it aside.

Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests