500 Doors

Five hundreds closed doors along a corridor are numbered from 1 to 500.
A person walks through the corridor and opens each door.
A 2nd person walks through the corridor and closes every alternate door.

Continuing in this manner, the i-th person comes and toggles (opened becomes closed, vice-versa) the position of every i-th door starting from door i.

Question: Which of the 500 doors are open after the 500-th person has walked through.

[HINT]: Solving such abstract problem, it helps to visualize on small sample (eg. 10 doors) to find the pattern.

Initial doors: (All closed)
■■■■■■■■■■
After 1st person (open all doors)
□□□□□□□□□□

After 2nd person
□■ □ ■□ ■ □■ □ ■

After 3rd person (toggles all 3n doors)
□■[■]■□[□]□■[■]■

After 4th person (toggles 4n)
□■ ■[□]□□□[□]■■

After 5th person (toggles 5n)
□■ ■ □[■]□□□■[□]

After 6th person (toggles 6n)
□■ ■ □ ■[■]□□■□

After 7th person (toggles 7n)
□■ ■ □ ■ ■[■]□■□

After 8th person (toggles 8n)
□■ ■ □ ■ ■ ■[■]■□

After 9th person (toggles 9n)
□■ ■ □ ■ ■ ■ ■[□]□

After 10th person (toggles 10n)
□■ ■ □ ■ ■ ■ ■ □[■]
Notice the 3 open doors are: {1, 4, 9}.

Do they give you any clue ?

They are all perfect square:
1 = 1^{2}
4 = 2^{2}
9 = 3^{2}

For 20 doors, we can get the 4 open doors : {1, 4, 9, 16}.
16 = 4^{2}

Therefore,
for 500 doors there will be N open doors:
N = \sqrt {500} = 22.36
22^2 = 484

Answer: the open doors are:
{1, 4, 9, 16, 25, 36, 49, …, 484}

Proof:
Perfect square has odd number of divisors.
4 : {1, 2, 4} (odd) 3 divisors
9: {1, 3, 9} (odd) 3 divisors
16: {1, 2, 4, 8, 16} (odd) 5 divisors
but
8: {1, 2, 4, 8} (even) 4 divisors

For an open door, after even number of toggles will close it, but odd number of toggles will open it again, hence all doors of perfect square will be open.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s