# Puzzles or short exercises illustrating mathematical problem solving to freshman students

At high school, the solution method to almost all mathematical exercises is to apply some technique or algorithm you have learned before. At the university, the situation is fundamentally different. Many exercises have the flavor of little research problems, where it is not obvious at all how to start. This new experience can be frustrating even to the most talented students.

I'm looking for puzzles or small exercises to illustrate "mathematical problem solving" to freshman students. Ideally, such a problem statement meets the following requirements:

• Easy to understand. The involved notions should be familiar from high school mathematics or daily live, and not be built upon a framework of abstract definitions. Suitable problems often come from combinatorics, elementary geometry or elementary number theory. Some abstractness is ok, since this is another point freshman students have to get used to.

• Exciting or fascinating in some way. No dry theory questions.

• The question should be suitable to get your hands on and "do reasearch" with it (if necessary, by giving hints). For example by looking at special cases, investigating the consequences of modified requirements, etc.

• The solution should not be obvious and require some clever idea. Furthermore, it should be possible to give a rigorous solution/proof, without involving long calculations, and like the question, only relying on methods which are well-known to a freshman student.

I will some give some examples of good problems (in my opinion) as answers below.

5 points are placed on a sphere. Show that there is a (closed) hemisphere which contains at least 4 points.

You can give a hint of "If we blindly take any cut of the sphere, by the pigeonhole principle, one of these hemispheres must contain at least 3 points."

Answer: Take any 2 points, and consider their great circle, which forms 2 hemispheres. By the Pigeonhole principle, out of the remaining 3 points, at least one of them must have 2 points on it. Hence we are done.

• Yeah, I really would like to have some problem of this flavor, a "hidden" application of the pigeonhole principle. However, the trick to exploit the boundary points might feel a bit like cheating. – azimut Sep 22 '13 at 21:25
• @azimut There would be several, where we look at getting better bounds than the naive pigeonhole. An example will be "The integers 1 to 10 are placed around the circle. What is the minimum of the maximum of sum of 3 consecutive integers?" Blind PP yields $\lceil\frac{165}{10} \rceil = 17$, and you can challenge them to find an example. Smart PP yields $\lceil \frac{54}{3} \rceil = 18$. – Calvin Lin Sep 22 '13 at 21:32
• @azimut This is another smart PP approach, where the 9 numbers cases was only done by exhaustive search, until I pointed out a simple version (and got the necromancer badge :) ). Sadly, I can't do the 8 numbers case. – Calvin Lin Sep 22 '13 at 21:36
• This is a good one. But my favorite pigeonhole problem is the old IMO question: Given a set of ten integers from the interval from $1$ to $100$, show that there are two disjoint subsets with equal sums. – Jyrki Lahtonen Sep 23 '13 at 18:50
• Very nice, but I think the so-called "hint" here is rather misleading. Adding emphasis to the word "blindly" would be better. – user1551 Oct 21 '13 at 18:37

There is a thin horizontal railing, say 10 ft long, running North/South. At time $t=0$ one hundred ants fall onto the railing, at random locations and each initially facing randomly either North or South. Upon making contact with the railing all the ants begin a forward march at the speed of 10 ft per minute. The railing is thin so that whenever two ants knock antlers, they both immediately turn on their six heels and start heading in the opposite direction. Whenever an ant reaches the end of the railing, it gently floats to the ground and stays there.

How long will it take for the railing to be clear of ants in the worst case? Assume that the ants are pointlike and need zero time to turn.

No hint here. A spoiler only:

What would change, globally speaking, if the ants would be able to walk thru each other?

If no light bulb flashes quickly, one may be to try with two, three, four ants... Often a good approach to try a simpler case first.

• This is really a nice one, I almost had forgot about it. Thanks! – azimut Sep 22 '13 at 21:25
• I would be interested in knowing how ants gently float to the ground. – Calvin Lin Sep 22 '13 at 21:43
• @Calvin: I used creative license there. Or copied the phrase from the game Angband, where that's how it is described, when your character falls to a spiked pit, but has earned the appropriate boon. – Jyrki Lahtonen Sep 23 '13 at 4:26
• The boon is called "feather fall" which may or may not explain why the verb "float" is used even though no liquid is involved ;-) – Jyrki Lahtonen Sep 23 '13 at 18:47
• Harder, more interesting followup question: now the rail is a circle of circumference 10 feet. What is the probability all ants end up at their starting points after one minute? – user7530 Nov 16 '13 at 18:26

The locker puzzle:

In a hallway there are 100 closed lockers. Now 100 persons pass the hallway. The first one changes the state (open or closed) of every locker. The second one changes the state of every second locker, the third person of every third locker and so on.

Which lockers will be open in the end?

(Answer: The lockers whose position is a perfect square.)

One can investigate this problem by doing it explicitely for numbers like 10 or 20. If some results are found, the correct answer can be conjectured. The last step is then to rigorously prove the conjecture.

"Sam Loyd's" 14-15 Puzzle

Can the tiles in the below arrangement be put in order by just sliding them around? (Answer: No. Every legal move retains the parity of the sum of the number of inversions and the row number that the blank appears on. It is easy to see that the given position has odd parity, and the home position has even parity.)

The solution might be a tad advanced, but with some guidance I think it is attainable. Since it was a (short-lived) craze in the 1880s, it must be fascinating and exciting!

• While admittedly this is a very nice problem with a great historical background, I'm worried that it might be a bit too hard to guide an average freshman student to the solution. – azimut Sep 22 '13 at 19:34
• @azimut: Yes, I thought that might be the case. But I thought I'd at least put it out there since I find it a great example of a simple puzzle that anyone can understand with a quite ingenious mathematical solution. – user642796 Sep 22 '13 at 19:47
• @azimut, not really. It is addictive; at least it was in a period. I don't think the money offered was the only reason people found it addictive. – Cyriac Antony Jan 18 '19 at 4:59

This is a classical one (On wikipedia):

Given an $8 \times 8$ grid where two diagonally opposite corner squares are removed. Is it possible to cover the 62 remaining squares by rectangles of size $2\times 1$?

(Answer: Imagine the squares of the grid are colored in black and white like a chessboard...)

Here, one can look at smaller boards first, and modify the pattern of the removed squares (don't remove any square; remove a single square; remove two adjacent corner squares, etc.).

One of my favourites is the game of 15, in which people take turns picking numbers from 1 to 9 (without repeating) and try to get three of them that add up to 15. Try and devise a winning strategy for it.

Hint: It teaches people about isomorphism.

I've found the following in the book The Man Who Loved Only Numbers about Paul Erdős. It is a little gem in my opinion:

Let $n$ be a positive integer. True or false: Each subset of $\{1,\ldots,2n\}$ of size $n + 1$ contains a pair of coprime numbers.

Ways of experimenting with this problem include looking at special cases for small $n$, and looking at subsets of different size (especially $n$ instead of $n+1$).

A man starts at the bottom of a mountain at 8 am and reaches the top at noon. He spends the night at the peak and starts down the mountain at 8 am the next day, reaching the bottom at noon. He follows the only path that exists on both days. Show that there must be at least one point on the path that he occupied at the same time each day.

Spoiler: A hint is given below.

The hint is to think of his 2 journeys as happening simultaneously.

There are 2 points on earth that are diametrically opposite to each other, and have the same temperature and pressure.

You can ask them to show that on the equator, there are 2 points diametrically opposite to each other, which have the same temperature.

Uses Intermediate Value Theorem, and they might have seen the 2-D version in high school already.

• This is quite a surprising statement, I agree. But I don't see how to give a short rigorous proof which is only based on high school mathematics. – azimut Sep 22 '13 at 19:37
• @azimut True, I was thinking of the 2-D version which is just Intermediate value theorem. The 3-D version uses Borsuk-Ulam, which might elicit a "huh". – Calvin Lin Sep 22 '13 at 19:44

How many squares are on a chess board?

You can ask it about a Go board too but not many kids have seen that.

Question is about counting squares of ALL sizes.

Answer for an $n*n$ board is $1^2+2^2+\cdots+n^2$.

Illustration for boards of different sizes.

Domino tiling

How many ways are there to tile a $2\times n$ rectangle by dominoes of size $1\times 2$?

Visualization of the tilings for $n\leq 6$: The problem can be investigated for small $n$ and has a surprising answer (Fibonacci numbers). The formal proof relies on induction and is a nice way to apply and watch this technique in a quite visible way.