It’s day 4 of the #loveyourmath campaign! One of the things I enjoy about doing mathematics is working on interesting problems that require a bit of creativity and/or cleverness. I especially like problems that don’t require you to know very much in advance. A few semesters ago we launched a course for mathematics majors, called MAT 220: Introduction to Mathematical Reasoning, whose main objective is to make students wrestle with exactly the types of problems I love. In particular, the focus of the course is on reasoning and communication through problem solving and written mathematical arguments in order to provide students with more experience and training early in their university studies. The goal is for the students to work on interesting yet challenging multi-step problems that require almost zero background knowledge. The hope is that students will develop (or at least move in the direction of) the habits of mind of a mathematician. The problem solving of the type in this course is a fundamental component of mathematics that receives little focused attention elsewhere in most mathematics programs.

Below are 15 problems from the course. Originally I was only going to list 5, but it was hard enough to only pick 15. I attempted to showcase a variety of problems that utilize different ways of thinking. I’m intentionally not providing any solutions. Some of these problems are classics or variations on classics. Have fun playing!

- I have 10 sticks in my bag. The length of each stick is an integer. No matter which 3 sticks I try to use, I cannot make a triangle out of those sticks. What is the minimum length of the longest stick?
- A mouse eats his way through a 3 by 3 by 3 cube of cheese by tunneling through all 27 of the 1 by 1 by 1 sub-cubes. If she starts at one corner and always moves to an uneaten sub cube, can she finish at the center of the cube?
- We have two strings of pyrotechnic fuse. The strings do not look homogeneous in thickness but both of them have a label saying 4 minutes. So we can assume that it takes 4 minutes to burn through either of these fuses. How can we measure a one minute interval?
- Show that in any group of 6 students there are 3 students who know each other or 3 students who do not know each other.
- Suppose someone draws 20 random lines in the plane. What is the maximum number of intersections of these lines?
- Suppose you have 12 coins, all identical in appearance and weight except for one that is either heavier or lighter than the other 11 coins. What is the minimum number of weighing one must do with a two-pan scale in order to identify the counterfeit?
- Suppose you have 9 coins, all identical in appearance and weight except for one that
*we know is heavier*than the other 8 coins. What is the minimum number of weighing one must do with a two-pan scale in order to identify the counterfeit? - Four prisoners are making plans to escape from jail. Their current plan requires them to cross a narrow bridge in the dark that has no handrail. In order to successfully cross the bridge, they must use a flashlight. However, they only have a single flashlight. To complicate matters, at most two people can be on the bridge at the same time. So, they will need to make multiple trips across the bridge, returning the flashlight back to the first side of the bridge by having someone walk it back. Unfortunately, they can’t throw the flashlight. It takes 1, 2, 5, and 10 minutes for prisoner A, prisoner B, prisoner C, and prisoner D to cross the bridge and when two prisoners are walking together with the flashlight, it takes the time of the slower prisoner. What is the minimum total amount of time it takes all four prisoners to get across the bridge?
- How many ways can 110 be written as the sum of 14 different positive integers?
- Consider the following problem. An overfull prison has decided to terminate some prisoners. The jailer comes up with a game for selecting who gets terminated. Here is his scheme. 10 prisoners are to be lined up all facing the same direction. On the back of each prisoner’s head, the jailer places either a black or a red dot. Each prisoner can only see the color of the dot for all of the prisoners in front of them and the prisoners do not know how many of each color there are. The jailer may use all black dots, or perhaps he uses 3 red and 7 black, but the prisoners do not know. The jailer tells the prisoners that if a prisoner can guess the color of the dot on the back of their head, they will live, but if they guess incorrectly, they will be terminated. The jailer will call on them in order starting at the back of the line. Before lining up the prisoners and placing the dots, the jailer allows the prisoners 5 minutes to come up with a plan that will maximize their survival. What plan can the prisoners devise that will maximize the number of prisoners that survive? Some more info: each prisoner can hear the answer of the prisoner behind them and they will know whether the prisoner behind them has lived or died. Also, each prisoner can only respond with the word “black” or “red.”
- In the senate of the Klingon home world no senator has more than three enemies. Show that the senate can be separated into two houses so that nobody has more than one enemy in the same house.
- 100 prisoners are isolated in individual jail cells with no way to communicate. They are currently serving life sentences. Due to an overcrowded prison, the jailer decides to offer the prisoners the following deal. There is a a room with nothing in it except a light switch (that starts in the off position). At random, the jailer will escort a single prisoner into the room with the light switch. After 5 seconds, the jailer will escort the prisoner back to his/her jail cell. The jailer will repeat this over and over again. He tells each of the prisoners that if one of the prisoners can indicate when every prisoner has been in the room with the light switch at least once, he will let all the prisoners go. However, if a prisoner erroneously states that each prisoner has been in the room with the light switch, then all the prisoners will be executed. Before beginning, the jailer gets all 100 prisoners together and gives them 5 minutes to come up with a plan. What should their plan be? It’s important to note that the jailer is choosing prisoners at random to take in the room. That is, by chance, the same prisoner may be escorted to the room several times in a row. Also, your task is to devise a scheme for the prisoners to communicate with the light switch. You shouldn’t bother searching for other ways for the prisoners to communicate.
- Three boxes, one with black, one with white, and one with black and white balls. Each of the boxes is labeled B, W, and BW, but unfortunately,
*all*the boxes are labeled incorrectly. Moreover, you cannot see inside each of the boxes, but you can reach in and pull a ball out. What is the minimum number of balls that need to be pulled before you can relabel all the boxes correctly? - Imagine you have 25 pebbles, each occupying one square on a 5 by 5 chess board. Suppose that each pebble must move to an adjacent square by only moving up, down, left, or right. Is it possible to do this if every pebble must move and each square is only occupied by a single pebble after all pebbles have moved? If so, find a solution. If not, explain why.
- Show that in any set of seven different positive integers there are three numbers such that the greatest common divisor of any two of them leaves the same remainder when divided by three.

If you want to see more problems from the course, go here.

*Note:* The #loveyourmath 5-day campaign is sponsored by the Mathematical Association of America. The goal of the campaign is to engage a general audience across a broad representation of mathematics, whether it is biology, patterns, textbooks, art, or puzzles.

Mathematics & Teaching

Northern Arizona University

Flagstaff, AZ

Website

928.523.6852

Twitter

Instagram

Facebook

Strava

GitHub

arXiv

ResearchGate

LinkedIn

Mendeley

Google Scholar

Impact Story

ORCID

MAT 226: Discrete Math

MAT 690: CGT

This website was created using GitHub Pages and Jekyll together with Twitter Bootstrap.

Unless stated otherwise, content on this site is licensed under a Creative Commons Attribution-Share Alike 4.0 International License.

The views expressed on this site are my own and are not necessarily shared by my employer Northern Arizona University.

The source code is on GitHub.

Flagstaff and NAU sit at the base of the San Francisco Peaks, on homelands sacred to Native Americans throughout the region. The Peaks, which includes Humphreys Peak (12,633 feet), the highest point in Arizona, have religious significance to several Native American tribes. In particular, the Peaks form the Diné (Navajo) sacred mountain of the west, called Dook'o'oosłííd, which means "the summit that never melts". The Hopi name for the Peaks is Nuva'tukya'ovi, which translates to "place-of-snow-on-the-very-top". The land in the area surrounding Flagstaff is the ancestral homeland of the Hopi, Ndee/Nnēē (Western Apache), Yavapai, A:shiwi (Zuni Pueblo), and Diné (Navajo). We honor their past, present, and future generations, who have lived here for millennia and will forever call this place home.