Take me to the INDEX of Blogs

I love math puzzles, especially those that require some logical thinking.

Here, I have an example of a puzzle that you can solve by brute force;

but using some logic, the puzzle becomes deliciously beautiful.

__I look at a simpler version of the puzzle to show brute-force solution:__

Joan is in a room that has five bulbs (B1, B2, B3, B4 and B5).

Each bulb can be individually switched ON and OFF by pulling a cord attached to it.

**Initially, all bulbs are OFF.**

Step 1: Joan pulls the cord on each bulb and they are all ON.

Step 2: Joan now pulls cord on every second bulb

Step 3: Joan pulls cord on every third bulb

Step 4: Joan pulls cord on every fourth bulb

Step 5: Joan pulls cord on every fifth bulb

**Which bulbs are ON at the end of Step 5?**

__Brute-Force Solution:__We can follow the sequence:

Step 1: By pulling cord on each bulb, Joan switches them all ON - all five bulbs B1, B2, B3, B4 and B5 are ON

Step 2: Joan pulls cord on bulbs B2 and B4 and they will be switched off.

The situation is;

B1 - ON; B2 - OFF; B3 - ON; B4 - OFF; B5 - ON

Step 3: Joan pulls cord on B3 and it is switched OFF.

Now: B1 - ON; B2 - OFF; B3 - OFF; B4 - OFF; B5 - ON

Step 4: Joan pulls cord on B4 and it is switched ON.

Now: B1 - ON; B2 - OFF; B3 - OFF; B4 - ON; B5 - ON

Step 5: Joan pulls cord on B5 and it is switched OFF.

Now: B1 - ON; B2 - OFF; B3 - OFF; B4 - ON; B5 - OFF

**Bulbs 1 and 4 are ON after Joan finishes step 5.**

I have tried brute-force method for 10 bulbs and the answer is that bulbs 1, 4 and 9 are ON.

**The answer gives us a clue that bulbs that are at whole square numbers are left ON after the iteration. For 100 bulbs, bulbs**

**1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 will be ON.**

**Why is it so?**

__In the beginning__all bulbs are OFF. At the end of the ON/OFF/ON/OFF....sequence -

*a bulb will be OFF if its cord is pulled an even number of time*but

*it will be ON if the cord is pulled an odd number of times*.

Bulbs at prime numbers will only be pulled twice (step 1 and step of prime number) so they will be OFF.

Let us look at the factors of some non-prime numbers:

12: Factors are 1,2,3,4,6,12 - 6 factors - even - bulb B12 will be OFF

20: Factors are 1,2,4,5,10,20 - 6 factors - even - bulb B20 will be OFF

44: Factors are 1,2,4,11,22,44 - 6 factors - even - bulb B44 will be OFF

72: 1,2,3,4,6,8,9,12,18,24,36,72 - 12 factors - even - bulb B72 will be OFF

In fact,

**all numbers that are not whole squares can be shown to have even number of factors and will therefore be OFF.**

Now look at the factors of numbers that are whole squares:

16 - 1,2,4,8,16 - five factors - odd - bulb B16 will be ON

25 - 1,5,25 - three factors - odd - bulb B25 will be ON

64 - 1,2,4,8,16,32,64 - seven factors - odd - bulb at B64 will be ON

and so on.

Why is it so? - If you look at the factors of non-whole-square numbers, you notice that factors come in pairs: 72 has (1,72 and 72,1); (2,36 and 36,2) etc. This makes the total number of factors to always be an even number.

In whole-square numbers the square root makes its own pair and the number of factors is always an odd number - for example:

36 - has (1,36 and 36,1); (2,18 and 18,2); (3,12 and 12,3); (4,9 and 9,4); (6,6) - total factors are nine - an odd number.

Hope you enjoyed the puzzle.

*Finally: Do you know that 1729 is a special number such that the sum its digits (=19) multiplied by the reverse the digits in the sum (=91) is equal to 1729; that is 19 x 91 = 1729!*

*Besides 1 and 81, 1458 is the only other number that I know which has this property.*