—
A group of students and teachers from our college used to run a math circle for the students of nearby schools before Covid struck. Apparently it used to be quite active. Now that the lockdown era is over, the math circle is being resurrected.
A bunch of volunteers including our teachers are working to get the programme running and one of my friends was among those who were tasked with finding math problems to help the participants of the math circle develop greater interest in mathematics.
So my friend spent some time searching for math puzzles and found a few. One of them was quite simple to understand (once we got to know the answer, that is 😅) and he told us about it.
I try to describe this puzzle and its solution in this blog post.
Imagine a frog which can only move horizontally towards left or right. It cannot move in any other direction.
When it moves for the first time, it takes one step. During each successive move it makes afterwards, it takes one step more than the number of steps it took during the previous move.
It will be something like this:
| Move# | 1st | 2nd | 3rd | 4th | 5th | .....
|------------+-----+-----+-----+-----+-----|
| Step count | 1 | 2 | 3 | 4 | 5 | .....
ie, the frog first takes one step, then two steps, afterwards three steps, and so on.
And upon starting each move, the frog has the option to change the direction of its movement (ie, left or right).
All steps within the same move will be made in the same direction.
The puzzle is to figure out whether it is possible for the frog to come back to the position from where it started by the time it finishes making its 10th move.
We need to find if it's possible for the frog to return to its starting position in 10 moves.
We could think of the starting position as 0, leftward
movements as negative numbers and rightward movements as positive
numbers whose value is the number of steps taken in that move.
Sort of like:
negative positive
<--------- 0 --------->
left right
Then our puzzle reduces to checking if an arithmetic expression's value is zero.
For example, if the frog moved like
1-Left, 2-Right, 3-Left
we could represent the movements with the following arithmetic expression:
-1 + 2 - 3
Before going into the actual puzzle, where the number of movements (let's call that move count) is 10, let's have a casual glance at a few examples where the frog can actually return to its starting location.
| Move | Move |
| count | sequence |
|-------+-------------------------|
| 3 | +1 +2 -3 |
| 3 | -1 -2 +3 |
| 4 | +1 -2 -3 +4 |
| 7 | -1 -2 +3 +4 -5 -6 +7 |
| 8 | +1 -2 -3 +4 +5 -6 -7 +8 |
| 8 | +1 +2 +3 +4 -5 -6 -7 +8 |
The positive numbers represent rightward movement and the negative numbers indicate leftward movement.
The sum of the numbers in each case is zero, meaning that the frog can return to its starting position if following one of these paths.
The frog moves 10 times. For move number n, it takes
n steps. And it has the option to change movement direction
at the beginning of each move.
So we could represent the movements like:
1 ± 2 ± 3 ± 4 ± 5 ± 6 ± 7 ± 8 ± 9 ± 10
We need to know if this arithmetic expression can turn out to be zero.
In this expression, there are 5 even numbers and 5 odd numbers.
| Odd | 1 | 3 | 5 | 7 | 9 |
|------+---+---+---+---+----|
| Even | 2 | 4 | 6 | 8 | 10 |
Let's focus on just the even numbers.
2 4 6 8 10
We know that addition or subtraction performed between two even numbers will always result in an even number.
even + even = even
even - even = even
Like:
4 + 2 = 6
4 - 2 = 2
ie, no matter whether we use addition or subtraction between these 5 even numbers, it will end up being an even number itself.
2 ± 4 ± 6 ± 8 ± 10
| | | | |
+--+--+ +--+--+ |
| | |
even ± even |
| | |
+-----+-----+ |
| |
even ± |
| |
+--------+------+
|
even
So the operations on the even numbers result in an even number.
Now, consider the odd numbers.
We know that
odd - odd = even
odd + odd = even
As in:
3 - 5 = -2
3 + 5 = 8
In our case, we have 5 odd numbers.
1 3 5 7 9
Let's group the odd numbers into pairs.
This leaves one of the odd numbers without a pair. Let it be
9.
1 3 5 7 9
| | | |
+--+ +--+
The addition/subtraction operations done on each odd number pair will result in an even number.
1 ± 3 ± 5 ± 7 ± 9
| | | | |
+--+--+ +--+--+ |
| | |
even ± even |
| | |
+-----+-----+ |
| |
even ± odd
Which results in an even number and an odd number.
Recall that we got another even number, which is the contribution of the 5 even numbers that we had considered earlier.
So we are left with 2 even numbers and an odd number.
even ± even ± odd
| |
+------+-----+
|
even
Addition/subtraction done on the two even numbers will result in an even number.
And we are left with an even number and an odd number.
even ± odd
We know that:
even + odd = odd
even - odd = odd
As in:
4 + 5 = 9
4 - 5 = -1
ie, addition/subtraction done between an even and odd number is going to result in an odd number.
This means that the result of:
1 ± 2 ± 3 ± 4 ± 5 ± 6 ± 7 ± 8 ± 9 ± 10
is an odd number.
Since 0 is not odd, the result cannot be
0.
Therefore, the frog cannot return to its initial location by the time it finishes moving for the 10th time.
∎
Acknowledgements: Thanks to Aditya, the friend mentioned in this blog post, who told us about this puzzle and its solution/proof.