Thursday, 8 February 2018

Math Puzzles - How logical approach makes them much more delicious

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.

Post a Comment