A number theory problem by Dang Anh Tu

Number Theory Level 3

There are 2000 students standing in the school yard. The mathematics professor wants to select a lucky student to represent the school at a competition.
He gets all the students to line up in a long row, and gives them a number from 1 to 2000. Then, he asks those with an odd number to leave, as they are not lucky enough.
With those that remain, he orders them again from 1 to 1000. Those which have an odd number are told to leave, as they are not lucky enough.
The professor repeats this process again and again until there is only 1 student left in this row.
What is the initial number that was given to the student who remained?

Image credit: Wikipedia B.kedar

The answer is 1024.

4 solutions

Suradnyana Wisnawa
Jun 3, 2014

I try to make a 1-20 students, and get student number 16 as the only student left. We know that the only student left is the student who kept a number that still possible to devide by 2 till the end. In other word, the number is $2^{n} < x$ where x is the total number of students.
For x = 2000, the maximum $2^{n} = 2^{10} = 1024$

Wisnawa, this is the fastest and simple way. Nice!

Dang Anh Tu - 7 years ago

Thanks! I figure it out as a $2^{n}$ number, but not sure untill I try make a mini sample

Suradnyana Wisnawa - 7 years ago

same way brother...................

ashutosh mahapatra - 7 years ago

Thats great, thank you

Suradnyana Wisnawa - 7 years ago

Milind Joshi
Jun 3, 2014

Suppose the number which was kept by the student in the main row is x.
1-2000 students are there...... 1st step..after removing odd nos.1-1000..x will become x/2......2nd step..1-500..x will become (x/2)/2=x/4......3rd step..1-250..x will become x/8........4th step..1-125..x will become x/16.......5th step..1-62..x/32..(63 students will be removed)......6th step..1-31..x/64........7th step..1-15..x/128......8th step..1-7..x/256....9th step..1-3..x/512.......10th step..only 1..x/1024.......After 10th step x/1024=1.......So x=1024

Yes, that's right, but you can read more from Wisnawa's post, this is the most simple way to explain how to find this number! Thank you and congratulations!

Dang Anh Tu - 7 years ago

Aravind Vishnu
Jul 18, 2014

the student's number is the greatest power of 2 under 2000

Martin Feussner
Jul 16, 2014

2^10= 1024 , since 10 rounds of reduction occur (2000>1000>500>250>125>62>31>15>7>3>1) and the person had to be the least possible even number (2) in the last round of reducing. (if this where not so he would not be the only person left)

A number theory problem by Dang Anh Tu

Image credit: Wikipedia B.kedar

The answer is 1024.

4 solutions

0 pending reports