The New Sudoku Players' Forum

[millie9]

Hi,

I need help in solving the following puzzle from this website

Code: Select all

100 people standing in a circle in an order 1 to 100.

No.1 has a sword.
He kills next person (i.e. no. 2) and gives sword to next to next (i.e no.3).
All person does the same until only 1 survives.

Which number survives at the last?

Answer is integer.

[creint]

Checked with excel and code and found a solution.
Spoiler:

Hidden Text: Show

It's 73 probably.

[millie9]

Checked with excel and code and found a solution.
Spoiler:

Hidden Text: Show

It's 73 probably.

Thanks. The answer is correct.

Can you pls explain your though process behind the answer. As still I've no clue how is the given number is correct.

[1to9only]

I found the survivor by this method (similar to pen and paper)!

Round 1, it helps to think of the 100 starters as paired, e.g. 1-2, 3-4 ... 99-100 - so 1 kills 2, 3 kills 4 ... 99 kills 100, and passes sword back to 1.

Code: Select all

1 2 3 4 5 6 ... 94 95 96 97 98 99 100 [1]
s k s k                   s  k  s  k   s


Round 2, still an even number (50) in circle and paired, e.g. 1-3, 5-7 ... 97-99 - so 1 kills 3 ... 97 kills 99, and passes sword back to 1.

Code: Select all

1 3 5 7 9 11 ... 87 89 91 93 95 97 99 [1]
s k s k                   s  k  s  k   s


Round 3, an odd number (25) in circle - so the 24th gets killed, the 25th gets the sword and kills number 1

Code: Select all

1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 [1 9]
s k s k                                                        s  k  s   k s


Round 4, 12 in circle

Code: Select all

9 17 25 33 41 49 57 65 73 81 89 97 [9]
s k  s  k              s  k  s  k   s


Round 5, 6 in circle

Code: Select all

9 25 41 57 73 89 [9]
s k  s  k  s  k   s


Round 6, 3 in circle

Code: Select all

9 41 73 [9]
s k  s   k


Survivor:

Code: Select all

73
s


s=sword, k=killed

[tarek]

There is a formula which escapes me now that tells the answer, and will also tell you the cycle the original ordinal and current ordinal

tarek

[tarek]

Remembered it now:

If the number of people in the circle can be expressed as (2^p)+x then the surviving person will be 2x+1. Now we can safely go for a circle of 10,000

For a programming challenge:
1. Number of cycles
2. Number of people remaining after each cycle
3. Original person ordinal when cycle and current ordinal are known
4. During which cycle a certain person is going to die when his original ordinal is known

tarek