A computer science problem by tanveen dhingra

Computer Science Level 2

There are 1600 people sitting around a circular table. The first person (person 1) has a sword and kills the second person then hands it to the next alive person (in this case person 3). Person 3 stabs person 4 and gives the sword to person 5. This goes on until person 1599 kills person 1600. Then person 1 kills person 3 and so on. This is repeated until there is only a single person remaining.

Who remains in the end?

Person 1155 Person 1153 Person 9 Person 1159

Tanveen Dhingra by tanveen dhingra , 19, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Aditya Raut
Oct 22, 2014

This problem is same as Who gets lucky in life

The answer's general formula is, that

if the number of people is n n and the power of 2 following n n is 2 k 2^k , then the person who survives is ( n − ( 2 k − n ) + 1 ) (n-(2^k-n)+1) , .ie. 2 n − 2 k + 1 2n - 2^k +1 .

In this case, it will be 2 × 1600 − 2048 + 1 = 3200 − 2048 + 1 = 1153 2\times 1600 - 2048 +1 = 3200-2048+1 = \boxed{1153}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Wow! How did you derive that formulae, @Aditya Raut ?

Anuj Shikarkhane - 6 years, 7 months ago

Log in to reply

Umm to be precise, intuitively :P No explanation right now... :(

Aditya Raut - 6 years, 7 months ago

https://en.wikipedia.org/wiki/Josephus_problem

The formula is implicit in the discussion.

It is a single line of code, which models the events directly and take just a few milliseconds to run:

list = Range [ 1600 ] ; While [ Length [ list ] > 1 , list = Drop [ RotateLeft [ list ] , 1 ] ; ] ; list [ [ 1 ] ] \text{list}=\text{Range}[1600];\text{While}[\text{Length}[\text{list}]>1,\text{list}=\text{Drop}[\text{RotateLeft}[\text{list}],1];];\text{list}[[1]]

A Former Brilliant Member - 2 years ago
Brock Brown
Jan 4, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
num_people = 1600
dead = set()
sword = 0 # person with sword
target = 1 # person targeted
# fight to the death
while len(dead) < num_people - 1:
    # find next target
    target = sword + 1
    if target == num_people:
        target = 0
    while target in dead:
        target += 1
        if target == num_people:
            target = 0
    # kill target
    dead.add(target)
    # pass sword
    sword += 1
    if sword == num_people:
        sword = 0
    while sword in dead:
        sword += 1
        if sword == num_people:
            sword = 0
print "Answer:", sword + 1

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Rajdeep Dhingra
Oct 22, 2014

Person 1153.

If you have any number of people equal to a power of 2 (2, 4, 8, etc.) then the first person will be the last remaining. The closest power of 2 to 1600 is 1024 (210). So the first person to go of the 1600 when there is 1024 people left will be the last person remaining. 1600 - 1024 = 576. 576 * 2 = 1152. Person 1152 will be the 576th person killed and person 1153 will be the first person to go of the remaining 1024 people.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...