Jump to content
BrainDen.com - Brain Teasers
  • 0

Execution Table


BMAD
 Share

Question

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?

Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 0

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………..

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...