## Sacrifice

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

### Sacrifice

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?

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

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

### Re: Sacrifice

What seems to me to be the natural solution is
Spoiler:
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.

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

### Re: Sacrifice

Smartass solution:
Spoiler:
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
<STUFF>

Spoiler:
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.

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

### Re: Sacrifice

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:
Spoiler:
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.

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

### Re: Sacrifice

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:
Spoiler:
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.

ThirdParty
Posts: 347
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

### Re: Sacrifice

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:
Spoiler:
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.

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

### Re: Sacrifice

ThirdParty wrote:Then the optimal solution is:
Use all N chickens that are available...

I like your optimal strategy for reasons you didn't fully explain:
Spoiler:
While your numbering scheme still requires a minimum of 7 chickens to be able to identify 101 cans (same as the first solution in this thread), the more chickens you use means the fewer chickens you actually risk. For example with 7 chickens you may possibly kill 5. With 8 chickens, you only ever risk 4. With 9 chickens, you risk a maximum of 3. It takes 14 chickens to reduce your risk to 2. (And trivially, 100 chickens to reduce it to 1.) Using more chickens to risk fewer seems counterintuitive at first.

ThirdParty
Posts: 347
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

### Re: Sacrifice

bjazz wrote:
ThirdParty wrote:Then the optimal solution is:
Use all N chickens that are available...

I like your optimal strategy for reasons you didn't fully explain:
Spoiler:
While your numbering scheme still requires a minimum of 7 chickens to be able to identify 101 cans (same as the first solution in this thread), the more chickens you use means the fewer chickens you actually risk. For example with 7 chickens you may possibly kill 5. With 8 chickens, you only ever risk 4. With 9 chickens, you risk a maximum of 3. It takes 14 chickens to reduce your risk to 2. (And trivially, 100 chickens to reduce it to 1.) Using more chickens to risk fewer seems counterintuitive at first.

Yes, that was my motivation: killing as few chickens as possible. A few small addenda:
Spoiler:
If we have 90 chickens and use all of them, we can't guarantee that no more than one chicken will die, but we can at least make it much more likely that no more than one chicken will die than it would have been if we'd only used 14 chickens.

Also, as a perhaps-insignificant factor, we'll end up feeding less of the safe juice to chickens if we use 90 chickens than if we only use 14, so will have more safe juice left over to feed to humans.

idonno
Posts: 300
Joined: Fri Apr 03, 2015 3:34 am UTC

### Re: Sacrifice

Tirear wrote:Smartass solution:

Real smartass solution
Spoiler:
0. Just let the humans drink one can every 24 hours. No one said anything about minimizing their deaths.

Assuming only one round like the first solution
Spoiler:
I think an adjustment to the first solution can be made to increase chicken survival. There are 128 possible combinations and you want to avoid combinations with the most deaths so when numbering cans, don't use the 7 death combination, the seven 6 death combinations and nineteen of the twenty-one 5 death combinations. This guarantees 2 chickens survive and there are really good odds of 3 chickens surviving.