There are infinitely many lightbulbs B1, B2, B3... Each can be either on or off.

Question

There are infinitely many lightbulbs B1, B2, B3... Each can be either on or off. Initially they are all off. Every time step. some of them will get toggled (turned on or off) according to the following rules:

1. At the 1st time step, all the bulbs are toggled (all turned on)

2. At the 2nd time step, the bulbs B2, B4, B6.. are toggled (only odd numbered bulbs are on)

3. .. and so on..

4. In general, the ith time step, the bulbs Bi, B2i, B3i... are toggled and so on

This process goes on forever. Which bulbs eventually stay on forever? Prove your answer.

Explanation / Answer

Every interger can be thought of as the product of two intergers. For example, 2 can be thought of as 1*2 and 2*1. Note that there are an even number of ways to "make" 2, representing two people who will switch B2. Now examine 4 in this same way. We get that 4 is 1*4, 2*2, 2*2, and 4*1. Notice that for 4, 2*2 and 2*2 are identical. Note that 1*4 and 4*1 are not identical, as they represent P1's 4th stop and P4's 1st stop. As of such, B4 the combinations are 1*4, 2*2, and 4*1. Note that B4 has an odd number of ways to "make" it. This is because each factorization has two "versions," the second being the "reversal" of the first (i.e. 1*4 and 4*1). This changed for 4 because it was a perfect square, and the "reversal" of the product of its square root (2*2) was the same as the original product. In otherwords B2-P2 is identical to B2-P2. Only the bulbs which are switched an odd number of times are left on in the end. Because of this, the bulbs that are left on in the end are the perfect squares.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.