Another mathematical puzzle

LifeIn

LifeIn

Well-known member
I saw this one on Numberphile and is looked neat:

There are 100 on/off switches and 100 people. All the switches are initially off. The first person comes to the switches and turns every one of them on. The second person flips ever 2nd switch, starting with switch #2. Since they are all on at this point, this results in every second switch being turned off. The third person comes and flips every 3rd switch starting with switch #3. The 4th person flips every 4th switch starting with switch #4, and so on. This continues all the way to the 100th person, who flips every 100th switch. Of course this means he just flips the last switch. The puzzle is to figure out which switches will be left on after all 100 people have finished doing their thing.

Here are some observations that may help. It is clear that after the first 10 people, the first 10 switches will never be flipped again. So it would be really easy to just work it out for the first 10 switches. This may or may not give you a clue to the final answer for all 100 switch. The next thing is that after person #50, the remaining people only get to flip one switch, because they already have to start past the half-way point.

You might guess the answer from what happens to the first 10 switches, but to really do the puzzle you should prove your answer rigorously. Hints in a couple of days if no one has gotten it.
 
LifeIn said:
I saw this one on Numberphile and is looked neat:

There are 100 on/off switches and 100 people. All the switches are initially off. The first person comes to the switches and turns every one of them on. The second person flips ever 2nd switch, starting with switch #2. Since they are all on at this point, this results in every second switch being turned off.
Click to expand...
This language is too ambiguous.

If the second person starts with switch #2, the second switch (for them) would be switch #3 - and thus NOT result in every other switch being turned off. Below is a representation of the first 10 switches as you've described (with the initial line representing no one having interacted with the switches yet. The second line is after the first person has switched them all. 0=off, 1=on):

#1#2#3#4#5#6#7#8#9#10
0000000000
1111111111
1101010101
110111000
1​

If the second person starts with switch #2, and flips every other switch, the first switch they change is #3
If the third person starts with switch #3 and flips every third switch, the first one they change is #5.

---

It seems to me that the language used to describe this needs to be specific. Does person #X start counting at position #X? Or do they all start counting at #1?

I think you meant the latter...

ps. having dabbled in software development, it might be inefficient, but wholly fun to write a program which would produce the answer in about 15 minutes.
 
mikeT said:
This language is too ambiguous.

If the second person starts with switch #2, the second switch (for them) would be switch #3 - and thus NOT result in every other switch being turned off. Below is a representation of the first 10 switches as you've described (with the initial line representing no one having interacted with the switches yet. The second line is after the first person has switched them all. 0=off, 1=on):

#1#2#3#4#5#6#7#8#9#10
0000000000
1111111111
1101010101
110111000
​
1​

If the second person starts with switch #2, and flips every other switch, the first switch they change is #3
If the third person starts with switch #3 and flips every third switch, the first one they change is #5.

---

It seems to me that the language used to describe this needs to be specific. Does person #X start counting at position #X? Or do they all start counting at #1?

I think you meant the latter...

ps. having dabbled in software development, it might be inefficient, but wholly fun to write a program which would produce the answer in about 15 minutes.
Click to expand...
The switches are numbered 1 to 100 and are all initially off. The first person flips them all from off to on. Think of that as flipping every 1th switch. The second person flips switch number 2, 4, 6, 8, 10, etc. At this point all the odd numbered switches are on and the even numbered ones are off. The third person flips every 3rd switch. So he flips switch 3 off (because it was on) and switch 6 on (because it was off) and so on with 9, 12, 15, etc. The 4th person flips switches 4, 8, 12, 16, etc. The 5th person flips switches 5, 10, 15, 20, etc. This continues until the 100th person flips switch 100.

What can we say about the switches that are left on at the end without having a computer program do it? I'll tell you this: Some of the switches left on at the end are 1, 4, 9, 16, and 25. Does that help?
 
Not sure I could prove this with maths, but each switch is flicked a number of times equal to its number of factors. If that is an odd number, the switch will be on a the end.

For your examples, 1 has 1, 4 has 3 (1, 2, 4), 9 has 3 (1, 3, 9), 16 has 5 (1, 2, 4, 8, 16) and 25 has 3 (1, 5, 25).
 
The Pixie said:
Not sure I could prove this with maths, but each switch is flicked a number of times equal to its number of factors. If that is an odd number, the switch will be on a the end.

For your examples, 1 has 1, 4 has 3 (1, 2, 4), 9 has 3 (1, 3, 9), 16 has 5 (1, 2, 4, 8, 16) and 25 has 3 (1, 5, 25).
Click to expand...

That is exactly right. So the question becomes, which numbers have an odd number of factors? Here is a hint on how to proceed to answer that question:

The Unique Factorization Theorem states that every number can be expressed in a unique way as a product of one or more primes. So for every number N, we can say...

N = p1^c1 * p2^c2 * p3^c3 * ... * pm^cm

where p1...pm are different primes and c1...cm are the exponents for each of those primes in the number N. So, for instance,

50 = 2^1 * 5^2

If we want to count the number of factors of 50 we only need to see how many ways we can write

2^a * 5^b where a<=1 and b<=2

For the exponent of 2 we can pick 0 or 1. That's two choices. For the exponent of 5 we can pick 0, 1, or 2. That's three choices. Any combination of these choices produces a different factor of 50. In this case they are:

2^0 * 5^0 = 1
2^0 * 5^1 = 5
2^0 * 5^2 = 25
2^1 * 5^0 = 2
2^1 * 5^1 = 10
2^1 * 5^2 = 50

And indeed 1, 5, 25, 2, 10, 50 are the only divisors of 50. Since there are an even number of them (6) your observative correctly implies that switch 50 will be off at the end. Only numbers with an odd number of factors will be on. Now go back to the way we wrote 50 as

2^1 * 5^2

The exponent "1" means we have 2 choices (0 and 1). The exponent "2" means we have 3 choices (0, 1, and 2). So the combination of choices is the product of the number of choices for each exponent, that is 2 * 3. With this example in mind, look again at the general case of

N = p1^c1 * p2^c2 * p3^c3 * ... * pm^cm

In finding divisors of N we only have to choose from (c1+1) choices for the exponent of p1, (c2+1) choices for the exponent of p2, etc. So the total number of combinations of choices is

(c1+1)*(c2+1)*(c3+1)*......*(cm+1)

This is the number of divisors of N. It can only be odd if all the individual terms in the product are odd. (In any one of them is even the product will be even). The only way those terms (ci+1) can all be odd is if all the ci are even. Can you figure out what sort of numbers N have this property?
 
Yesterday my son found a much simpler way to solve this puzzle where you don't need the Unique Factorization Theorem. Just consider the square root of each number. For every divisor, d, that is less than the square root of N there is corresponding factor, N/d, that is greater than the square root. Since they pair up like that there must be an even number of them.
 
Cool pattern. If you brute force the answer in excel it looks like this.

1
2 zeros,
1
4 zeros
1
6 zeros
1
8 zeros
. . .
18 zeros
1

Having some background with numbers it pops out as an obvious square pattern: i.e. The switch is on when N is a square, i.e. 1, 4,9,16,25,36,49,64,81,100

To prove the answer at the back of the book so to speak is the challenge.

-------------------------------------------------------------

If number of times switched is odd, the switch will be on, otherwise the switch will be off.

1) The number of times a switch will be flipped is equal to the number of divisors it has.

- For example 18 has 6 divisors (1, 2, 3, 6, 9, 18) and will be off at the end of the trial.​

2) The number of divisors it has will be pairs (i.e. even) unless one of those is its square root:

- For example 17 (1, 17) and 17 is a prime number. It has 2 divisors and will be off at the end of the trial.​

or

- For example 64 has 7 divisors (1, 2, 4, 8, 16, 32, 64) where 8 is the square root. It will be on at the end of the trial.​


3) Therefore, for a switch to be on at the end of the switching, it requires an integer square root.



It has been a while since I've done a mathematical proof, but I think that sufficiently gets to the gist of it.


Thanks. That was fun.
 
You must log in or register to reply here.
Back
Top