Execution Table

[BMAD]

I believe this question is a classic but I am unable to find it in the forums so I will venture the wrath of the moderator gods by posting it anyways:

"Only the smartest one shall survive," said the executioner. "All of you prisoners will be seated around this round table. I will chop off the head of the prisoner in seat #1, skip seat #2, chop #3, etc. Beheaded bodies (and chairs) will be cleared away post haste. When I get to the end I will continue to chop, skip, chop, until there is but one prisoner remaining, who will then be freed."

a) If there are 13 prisoners, which is the lucky seat number?

b) In the morning, you will be told how many prisoners, n. You must figure out the best seat quickly, just knowing n. Which seat, k, should you 'head' for, in order to be freed?

[TimeSpaceLightForce]

a)

xox

xxxoxx

xxxxxxxoxxxxx

[k-man]

a) 10

b) If n is a power of 2, then pick the chair n. If not, then find m that is the largest power of 2 smaller than n (m=2^{floor(log₂n)}). Pick the chair 2(n-m).

[plasmid]

I remember this one.

Admittedly something that cannot really be found using a search... unless you know that that version had "sword" and "kill", and you're willing to look through a few pages of search results.

[bgm1961]

I agree with Time - the intuitive and easy part of the answer is that the smartest person will choose

chair 8.

But calculating how to arrive at that answer vice using intuition will have to wait till after breakfast!

[bhramarraj]

It is clear that in first round all odd numbers will be executed.

Then on second round: dividing remaining even numbers by 2, the odd numbers we get will be executed.
The same will be repeated third time and so on.
In case of 13 persons, 6 persons will remain after first round, and three persons after second round and on third round only one will survive.
So 2*2*2 = 8 will be the survivor’s seat.
In case of 1 to 3 persons safe seat is no. 2.
In case of 4 to 7 persons, safe seat is no. 4.
In case of 8 to 15 persons, safe seat is no. 8.
In case of 16 to 31 persons, safe seat is no. 16.
In case of 32 to 63 persons, safe seat is no. 32.
The safe seat pattern is 2,4,8,16,32,64,128 and so on, corresponding to max. no. of persons as 3,7,15,31,63,127,255 and so on.
i.e. safe seat is:
2^1 for 2^1 to 2^0 + 2^1 Persons.
2^2 for 2^2 to 2^0 + 2^1 + 2^2 Persons,
2^3 for 2^3 to 2^0 + 2^1 + 2^2 + 2^3 persons.
2^4 for 2^4 to 2^0 + 2^1 +2^2 +2^3 +2^4 persons.
And so on………..

[bhramarraj]

It is clear that in first round all odd numbers will be executed.

Then on second round: dividing remaining even numbers by 2, the odd numbers we get will be executed.

The same will be repeated third time and so on.

In case of 13 persons, 6 persons will remain after first round, and three persons after second round and on third round only one will survive.

So 2*2*2 = 8 will be the survivor’s seat.

In case of 1 to 3 persons safe seat is no. 2.

In case of 4 to 7 persons, safe seat is no. 4.

In case of 8 to 15 persons, safe seat is no. 8.

In case of 16 to 31 persons, safe seat is no. 16.

In case of 32 to 63 persons, safe seat is no. 32.

The safe seat pattern is 2,4,8,16,32,64,128 and so on, corresponding to max. no. of persons as 3,7,15,31,63,127,255 and so on.

i.e. safe seat is:

2^1 for 2^1 to 2^0 + 2^1 Persons.

2^2 for 2^2 to 2^0 + 2^1 + 2^2 Persons,

2^3 for 2^3 to 2^0 + 2^1 + 2^2 + 2^3 persons.

2^4 for 2^4 to 2^0 + 2^1 +2^2 +2^3 +2^4 persons.

And so on………..

If n are the number of persons, and

n = 2^a to 2^0 + 2^1 + 2^2 + 2^3 + ..... + 2^a

Then 2^a is the safe seat for such a group of persons.

[BMAD]

a)

xox

xxxoxx

xxxxxxxoxxxxx

It is clear that in first round all odd numbers will be executed.

Then on second round: dividing remaining even numbers by 2, the odd numbers we get will be executed.

The same will be repeated third time and so on.

In case of 13 persons, 6 persons will remain after first round, and three persons after second round and on third round only one will survive.

So 2*2*2 = 8 will be the survivor’s seat.

In case of 1 to 3 persons safe seat is no. 2.

In case of 4 to 7 persons, safe seat is no. 4.

In case of 8 to 15 persons, safe seat is no. 8.

In case of 16 to 31 persons, safe seat is no. 16.

In case of 32 to 63 persons, safe seat is no. 32.

The safe seat pattern is 2,4,8,16,32,64,128 and so on, corresponding to max. no. of persons as 3,7,15,31,63,127,255 and so on.

i.e. safe seat is:

2^1 for 2^1 to 2^0 + 2^1 Persons.

2^2 for 2^2 to 2^0 + 2^1 + 2^2 Persons,

2^3 for 2^3 to 2^0 + 2^1 + 2^2 + 2^3 persons.

2^4 for 2^4 to 2^0 + 2^1 +2^2 +2^3 +2^4 persons.

And so on………..

If n are the number of persons, and

n = 2^a to 2^0 + 2^1 + 2^2 + 2^3 + ..... + 2^a

Then 2^a is the safe seat for such a group of persons.

correct answers

[k-man]

a)

xox

xxxoxx

xxxxxxxoxxxxx

It is clear that in first round all odd numbers will be executed.

Then on second round: dividing remaining even numbers by 2, the odd numbers we get will be executed.

The same will be repeated third time and so on.

In case of 13 persons, 6 persons will remain after first round, and three persons after second round and on third round only one will survive.

So 2*2*2 = 8 will be the survivor’s seat.

In case of 1 to 3 persons safe seat is no. 2.

In case of 4 to 7 persons, safe seat is no. 4.

In case of 8 to 15 persons, safe seat is no. 8.

In case of 16 to 31 persons, safe seat is no. 16.

In case of 32 to 63 persons, safe seat is no. 32.

The safe seat pattern is 2,4,8,16,32,64,128 and so on, corresponding to max. no. of persons as 3,7,15,31,63,127,255 and so on.

i.e. safe seat is:

2^1 for 2^1 to 2^0 + 2^1 Persons.

2^2 for 2^2 to 2^0 + 2^1 + 2^2 Persons,

2^3 for 2^3 to 2^0 + 2^1 + 2^2 + 2^3 persons.

2^4 for 2^4 to 2^0 + 2^1 +2^2 +2^3 +2^4 persons.

And so on………..

If n are the number of persons, and

n = 2^a to 2^0 + 2^1 + 2^2 + 2^3 + ..... + 2^a

Then 2^a is the safe seat for such a group of persons.

correct answers

Respectfully disagree.

Let's test this solution for 5 prisoners. Execution order will be 1,3,5,4 with #2 surviving.

For 13 prisoners: 1,3,5,7,9,11,13,4,8,12,6,2 with #10 survivng.

[BMAD]

I think we are interpreting the OP differently. In your case, as I read your answer, the executioner never stops, cutting in a circle until they are done. The way I meant for the op to be interpreted is that after the first run of kills, he/she starts back over and kills the new first person, continue through and starting over once they come to the end with the 'next' first person.

so with 13 people:round 1,, 1,3,5,7,9,11,13...round 2: 2,6,10...round 3: 4, 12...8 lives

I like your solution too though.

a)

xox

xxxoxx

xxxxxxxoxxxxx

It is clear that in first round all odd numbers will be executed.

Then on second round: dividing remaining even numbers by 2, the odd numbers we get will be executed.

The same will be repeated third time and so on.

In case of 13 persons, 6 persons will remain after first round, and three persons after second round and on third round only one will survive.

So 2*2*2 = 8 will be the survivors seat.

In case of 1 to 3 persons safe seat is no. 2.

In case of 4 to 7 persons, safe seat is no. 4.

In case of 8 to 15 persons, safe seat is no. 8.

In case of 16 to 31 persons, safe seat is no. 16.

In case of 32 to 63 persons, safe seat is no. 32.

The safe seat pattern is 2,4,8,16,32,64,128 and so on, corresponding to max. no. of persons as 3,7,15,31,63,127,255 and so on.

i.e. safe seat is:

2^1 for 2^1 to 2^0 + 2^1 Persons.

2^2 for 2^2 to 2^0 + 2^1 + 2^2 Persons,

2^3 for 2^3 to 2^0 + 2^1 + 2^2 + 2^3 persons.

2^4 for 2^4 to 2^0 + 2^1 +2^2 +2^3 +2^4 persons.

And so on..

If n are the number of persons, and

n = 2^a to 2^0 + 2^1 + 2^2 + 2^3 + ..... + 2^a

Then 2^a is the safe seat for such a group of persons.

correct answers

Respectfully disagree.

Let's test this solution for 5 prisoners. Execution order will be 1,3,5,4 with #2 surviving.

For 13 prisoners: 1,3,5,7,9,11,13,4,8,12,6,2 with #10 survivng.

[k-man]

I think we are interpreting the OP differently. In your case, as I read your answer, the executioner never stops, cutting in a circle until they are done. The way I meant for the op to be interpreted is that after the first run of kills, he/she starts back over and kills the new first person, continue through and starting over once they come to the end with the 'next' first person.

It's your puzzle, so your interpretation prevails. However, you mentioned that it's a 'classic' and the prisoners are in a circle, which, in my opinion, strongly suggests the classic interpretation of the problem known as the Josephus problem. The reason they are in a circle is that you don't stop at the end and start the next round with the 'next first person' as if they were in a row. That distinction is what makes this problem interesting, IMHO.

[BMAD]

fair enough. by classic, i only meant that I heard it long ago and assumed that it was somewhere buried in the forums (but could not be found by me).

I think we are interpreting the OP differently. In your case, as I read your answer, the executioner never stops, cutting in a circle until they are done. The way I meant for the op to be interpreted is that after the first run of kills, he/she starts back over and kills the new first person, continue through and starting over once they come to the end with the 'next' first person.

It's your puzzle, so your interpretation prevails. However, you mentioned that it's a 'classic' and the prisoners are in a circle, which, in my opinion, strongly suggests the classic interpretation of the problem known as the Josephus problem. The reason they are in a circle is that you don't stop at the end and start the next round with the 'next first person' as if they were in a row. That distinction is what makes this problem interesting, IMHO.