Who is Guilty?

I am running a PRIMES-STEP program for middle school students, where we try to do research in mathematics. In the fall of 2015 we decided to study the following topic in logic.

Suppose there is an island where the following four types of people live:

  • Absolute truth-tellers always tell the truth.
  • Partial truth-tellers tell the truth with one exception: if they are guilty, they will say that they are innocent.
  • Absolute liars always lie.
  • Responsible liars lie with one exception: if they are guilty, they will say that they are guilty.

See if you can solve this simple logic puzzle about people on this island.

It is known that exactly one person stole an expensive painting from an apartment. It is also known that only Alice or Bob could have done it. Here are their statements:
Alice: I am guilty. Bob is a truth-teller.
Bob: I am guilty. Alice stole it. Alice is the same type as me.
Who stole the painting and what types are Alice and Bob?

My students and I discovered a lot of interesting things about these four types of people and wrote a paper: Who Is Guilty?. This paper contains 11 cute logic puzzles designed by each of my 11 students.

I envied my students and decided to create two puzzles of my own. You have already solved the one above, so here is another, more difficult, puzzle:

A bank was robbed and a witness said that there was exactly one person who committed the robbery. Three suspects were apprehended. No one else could have participated in the robbery.
Alice: I am innocent. Bob committed the crime. Bob is a truth-teller.
Bob: I am innocent. Alice is guilty. Carol is a different type than me.
Carol: I am innocent. Alice is guilty.
Who robbed the bank and what types are the suspects?

Share:Facebooktwitterredditpinterestlinkedinmail

A Travel Puzzle

The following cute puzzle of unknown origins was sent to me by Martina Balagovic and Vincent van der Noort:

A car travels from A to B and back again. When going uphill it goes 56 km an hour, when going downhill it goes 72 km an hour and while driving on flat surface it goes 63 km an hour. Getting from A to B takes 4 hours and getting back (over the same road) takes 4 hours and 40 minutes.
What is the distance between A and B?

Share:Facebooktwitterredditpinterestlinkedinmail

Really Big Numbers

 

Really Big NumbersI received a book Really Big Numbers by Richard Schwartz for review. I was supposed to write the review a long time ago, but I’ve been procrastinating. Usually, if I like a book, I write a review very fast. If I hate a book, I do not write a review at all. With this book I developed a love-hate relationship.

Let me start with love. I enjoyed reading the first 80 pages. The pictures are great, and some explanations are very well thought out. Plus, I haven’t thought much about really big numbers, so the book helped me understand them. I was impressed with how this book treats very difficult ideas with simple explanations and illuminating images. I was captivated by it.

Now to hate. I had two problems with this book: one pedagogical and the other mathematical.

The pedagogical issue. The beginning of the book is suitable for small children. Most of the book is suitable for advanced middle-schoolers who like mathematics. The last part is very advanced. Is it a good idea to show children a book that looks like a children’s book, but which soon becomes totally out of their reach? Richard Schwartz understands it and says many times that pieces of this book might be read several years apart. Several years? What child is ready to wait several years to finish a book? How would children feel about the book and about numbers when no matter how hard they try, they cannot understand the end of the book?

As a reviewer, I can’t recommend the full book for kids who are not ready to grasp the notion of the Ackermann function or arrow notation. Even if the child is capable of understanding these ideas, there are mathematical issues that would prevent me from recommending it.

The mathematical issue. Let me start by explaining the notion of plex. We call an n-plex a number that is equal to 10n. For example, 2-plex means 102 which is 100, and 10-plex means 1010. The fun part starts when we plex plexes. The number n-plexplex means 10 to the power n-plex which is 10(1010). We can continue plexing: n-plexplexplex means 10 to the power n-plexplex. When you are hunting for really big numbers, it is easier to write the number of plexes rather than writing plexes after plexes. Richard Schwartz introduces the following notation to help visualize the whole thing. He puts numbers in a square. Number n in a square means 1-plexed n times. For example, 2 inside a square means 1010. Ten inside a square is 1-plexplexplexplexplexplexplexplexplexplex.

We can start nesting squares. For example, 2 inside a square means 1-plex-plex or 1010. Let’s add a square around it: 2 inside two squares means 1010 inside a square, which equals 1 plexed 1010 times. To denote 10 nested in n squares Richard Schwartz uses the next symbol: n inside a pentagon. For example, 1 inside a pentagon is 10 inside a square. I wrote this number in the previous paragraph: it is 1-plexplexplexplexplexplexplexplexplexplex. Similarly, n inside a hexagon means 10 inside n nested pentagons. We can continue this forever: n inside a k-gon is 10 inside k nested (k-1)-gons.

What bothers me is why a square? Why not a triangle? If we adopt this scheme, what is the meaning of a number in a triangle? Let’s try to unravel this. Following Richard Schwartz’s notation we get that n inside a square is the same as 10 inside n nested triangles. What do we do n times with 10 to get to 1 plexed n times? 1-plexed n times is 10 plexed n-1 times. There is a disconnect in notation here. For example, 10 in two nested triangles should mean 2 inside a square that is 1010. 10 inside one triangle should mean 1 inside a square which is 10. This doesn’t make any sense.

I started googling around and discovered the Steinhaus–Moser notation. In this notation a number n in a triangle means nn. A number n in a square means the number n inside n nested triangles. A number n in a pentagon means the number n inside n nested squares. And so on. This makes total sense to me. If we move down the number of sides, we can say that the number n inside a 2-gon means n times n and the number n inside a 1-gon means n. This is perfect.

Schwartz changed the existing notation in two places. First he made everything about 10. This might not be such a bad idea except his 10 inside a square doesn’t equal 10 inside a square in Steinhaus–Moser notation. In Steinhaus–Moser notation 10 inside a square means 10 plexed 10 times. The author removed one of the plexes. He made 10 inside the square to mean 1 plexed 10 times, and as a result it stopped working.

Even though the first 83 pages are delightful and the pictures are terrific, the notation doesn’t work. What a pity.

Share:Facebooktwitterredditpinterestlinkedinmail

A River-Crossing Puzzle

I have solved too many puzzles in my life. When I see a new one, my solution is always the intended one. But my students invent other ideas from time to time and teach me to think creatively. For example, I gave them this puzzle:

Two boys wish to cross a river, but there is a single boat that can take only one boy at a time. The boat cannot return on its own; there are no ropes or similar tricks; yet both boys manage to cross the river. How?

Here is what my inventive students came up with:

  • There was another person on the other side of the river who brought the boat back.
  • There was a bridge.
  • The boys can swim.
  • They just wanted to cross the river and come back, so they did it in turns.

And here is my standard solution: They started on different sides of the river.

I gave a talk about thinking inside and outside the box at the Gathering for Gardner conference. I mentioned this puzzle and the inventiveness of my students. After the conference a guy approached me with another answer which is now my favorite:

  • They wait until the river freezes over and walk to the other side.
Share:Facebooktwitterredditpinterestlinkedinmail

An Orthogonal Quadrangle

An Orthogonal Quadrangle

Consider a triangle with vertices A, B, and C. Let O be its orthocenter. Let’s connect O to the vertices. We get six lines: three sides of the triangle and three altitudes. These six lines are pair-wise orthogonal: AO ⊥ BC, BO ⊥ AC, and CO ⊥ AB.

It is easy to see that A is the orthocenter of the triangle OBC, and so on: each vertex is the orthocenter of the triangle formed by the other three. We say that these four points form an orthocentric system.

I heard a talk about this structure at the MOVES 2015 conference by Richard Guy. What I loved in his talk was his call to equality and against discrimination. The point O plays the same role as the other three points. It should be counted. Richard Guy suggested calling this system an orthogonal quadrangle. I am all for equality. This is not a triangle, this is a quadrangle!

Share:Facebooktwitterredditpinterestlinkedinmail

The Battle I am Losing

I want the world to be a better place. My contribution is teaching people to think. People who think make better decisions, whether they want to buy a house or vote for a president.

When I started my blog, I posted a lot of puzzles. I was passionate about not posting solutions. I do want people to think, not just consume puzzles. Regrettably, I feel a great push to post solutions. My readers ask about the answers, because they are accustomed to the other websites providing them.

I remember I once bought a metal brainteaser that needed untangling. The solution wasn’t included. Instead, there was a postcard that I needed to sign and send to get a solution. The text that needed my signature was, “I am an idiot. I can’t solve this puzzle.” I struggled with the puzzle for a while, but there was no way I would have signed such a postcard, so I solved it. In a long run I am glad that the brainteaser didn’t provide a solution.

That was a long time ago. Now I can just go on YouTube, where people post solutions to all possible puzzles.

I am not the only one who tries to encourage people to solve puzzles for themselves. Many Internet puzzle pages do not have solutions on the same page as the puzzle. They have a link to a solution. Although it is easy to access the solution, this separation between the puzzle and its solution is an encouragement to think first.

But the times are changing. My biggest newest disappointment is TED-Ed. They have videos with all my favorite puzzles, where you do not need to click to get to the solution. You need to click to STOP the solution from being fed to you. Their video Can you solve the prisoner hat riddle? uses my favorite hat puzzle. (To my knowledge, this puzzle first appeared at the 23-rd All-Russian Mathematical Olympiad in 1997.) Here is the standard version that I like:

A sultan decides to give 100 of his sages a test. He has the sages stand in line, one behind the other, so that the last person in line can see everyone else. The sultan puts either a black or a white hat on each sage. The sages can only see the colors of the hats on all the people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. Each person who guesses the color wrong will have his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?

The video is beautifully done, but sadly the puzzle is dumbed down in two ways. First, they explicitly say that it is possible for all but one person to guess the color and second, that people should start talking from the back of the line. I remember in the past I would give this puzzle to my students and they would initially estimate that half of the people would die. Their eyes would light up when they realized that it’s possible to save way more than half the people. They have another aha! moment when they discover that the sages should start talking from the back to the front. This way each person sees or hears everyone else before announcing their own color. Finally, my students would think about parity, and voilà, they would solve the puzzle.

In the simplified adapted video, there are no longer any discoveries. There is no joy. People consume the solution, without realizing why this puzzle is beautiful and counterintuitive.

Nowadays, I come to class and give a puzzle, but everyone has already heard the puzzle with its solution. How can I train my students to think?

Share:Facebooktwitterredditpinterestlinkedinmail

A Frog Puzzle

I stumbled upon a TED-Ed video with a frog puzzle:

You’re stranded in a rainforest, and you’ve eaten a poisonous mushroom. To save your life, you need an antidote excreted by a certain species of frog. Unfortunately, only the female of the species produces the antidote. The male and female frogs occur in equal numbers and look identical. There is no way to distinguish between them except that the male has a distinctive croak. To your left you spot a frog on a tree stump. You hear a croak from a clearing in the opposite direction, where you see two frogs. You can’t tell which one made the sound. You feel yourself starting to lose consciousness, and you realize that you only have time to run in one direction. Which way should you go: to the clearing and lick both frogs or to the tree stump and lick the stump frog?

My first thought was that male frogs croak to attract female frogs. That means the second frog in the clearing is probably an already-attracted female. The fact that the stump frog is not moving means it is male. I was wrong. This puzzle didn’t assume any knowledge of biology. The puzzle assumes that each frog’s gender is independent from other frogs. Thus this puzzle is similar to two-children puzzles that I wrote so much about. I not only blogged about this, but also wrote a paper: Martin Gardner’s Mistake.

As in two-children puzzles, the solution depends on why the frog croaked. It is easy to make a reasonable model here. Suppose the male frog croaks with probability p. Now the puzzle can be solved.

Consider the stump frog before the croaking:

  • It is a female with probability 1/2.
  • It is a croaking male with probability p/2.
  • It is a silent male with probability (1-p)/2.

Consider the two frogs in the clearing before the croaking:

  • Both are female with probability 1/4.
  • One is a female and another is a croaking male with probability p/2.
  • One is a female and another is a silent male with probability (1-p)/2.
  • Both are silent males with probability (1-p)2/4.
  • Both are croaking males with probability p2/4.
  • One is a silent male and another is a croaking male with probability p(1-p)/2.

The probabilities corresponding to our outcome—a non-croaking frog on the stump and one croaking frog in the clearing—are in bold. Given that the stump frog is silent, the probability that it’s a female is 1/(2-p). Simillarly, given that one clearing frog croaked, the probability that one of them is a female is 1/(2-p). The probabilities are the same: it doesn’t matter where you go for the antidote.

The TED-Ed’s puzzle makes the same mistake that is common in the two-children puzzles. I don’t want to repeat their incorrect solution. The TED-Ed’s frog puzzle is wrong.

(The calculation in the second to last paragraph was corrected on Nov 13, 2021.)

Share:Facebooktwitterredditpinterestlinkedinmail

Is My Bank Smart Enough?

When I receive a bank statement, I review all the transactions. The problem is my failing memory. I do not remember when and where I last took money from an ATM, and how much. So I decided to create a pattern. I used to take cash in multiples of 100. Probably most people do that. A better idea is to always take the amount that has a fixed remainder modulo 100, but not 0. For example, let’s say I take one of the following amounts: 40, 140, 240, or 340. Sometimes I need more money, sometimes less. This set of numbers covers all of my potential situations, but my pattern is that all the numbers end in 40. This way if someone else gets access to my account, they will almost surely take a multiple of 100. I will be able to discover a fraud without remembering the details of my last withdrawal.

In addition, when I first started doing this, I was hoping I wouldn’t need to wait until I review my own statement to discover problems. My hope was that if a thief tried to take cash from my account, my bank would notice a change in the pattern and notify me immediately. Now I realize that this was wishful thinking. I doubt that banks are as smart as I am.

One day I should try an experiment. I should go to an ATM I never use and withdraw 200 dollars. I wonder if my bank would notice.

Share:Facebooktwitterredditpinterestlinkedinmail

Late Homework

One of my jobs is giving linear algebra recitations at MIT. The most unpleasant aspect of it is dealing with late homework. Students attempt to submit their homework late for lots of different reasons: a sick parent needing help, stress, a performance at Carnegie Hall, a broken printer, flu, and so on. How do I decide which excuse is sufficient, and which is not? I do not want to be a judge! Moreover, my assumption is that people tell the truth. In the case of linear algebra homework, this assumption is unwise. As soon as students discover that I trust everyone, there’s a sharp increase in the number of sick parents and broken printers. So I have the choice of being either a naive idiot or a suspicious cynic. I do not like either role.

Our linear algebra course often adopts a brilliant approach: We announce that late homework is not allowed for any reason. To compensate for emergencies, we drop everyone’s lowest score. That is, we allow the students to skip one homework out of ten. They are free to use this option for oversleeping the 4 pm deadline. If all their printers work properly and they do not get so sick that they have to skip their homework, they can forgo the last homework. Happily, this relieves me from being a judge.

Or does it? Unfortunately, this policy doesn’t completely resolve the problem. Some students continue trying to push their late homework on me, despite the rules. In order to be fair to other students and to follow the rules, I reject all late homework. The students who badger me nonetheless waste my time and drain my emotions. This is very unpleasant.

From the point of view of those students, such behavior makes sense. They have nothing to lose and they might get some points. There is no way to punish a person who tries to hand in homework late and from time to time they stumble onto a soft instructor who accepts the homework against the official rules. Because such behavior is occasionally rewarded, they continue doing it. I believe that wrong behavior shouldn’t be rewarded. As a responsible adult, I think it is my duty to counteract the rewards of this behavior. But I do not know how.

What should I do? Maybe I should…

  1. Persuade our course leader, or MIT in general, to introduce a punishment for trying to hand in late homework. We might, for example, subtract points from their final score.
  2. Promote the value of honorably following the rules through discussions with the students.
  3. Growl at any student who submits their homework late.
  4. Explain to them what other people think about them, when they do not follow the rules.

Maybe I should just do number 4 right now and explain what I feel. A student who persists in handing in homework late feels to me that s/he is entitled and is better than everyone else, and shows that s/he doesn’t care about the rules and honor. Again, this wastes my time, puts me in a disagreeable position, and reduces my respect for that student.

Earlier I suggested that students don’t have anything to lose by such behavior, but in fact, they do pay a price, even though they may not understand that.

Share:Facebooktwitterredditpinterestlinkedinmail

An Asteroid Walk

I found the following puzzle on a facebook page of Konstantin Knop (in Russian):

Seven astronauts landed on a small spherical asteroid. They wanted to explore it and walked in different directions starting from the same location. All used the same walking algorithm: walk x kilometers forward, turn 90 degrees left and walk another x kilometers, turn 90 degree left again and walk the last x kilometers. The value of x was different for different astronauts and was one of 30, 40, 50, 60, 70, 80, and 90.
All but one astronaut finished in the same location. What was the value of x for the astronaut who finished alone? What is the size of the asteroid?

Share:Facebooktwitterredditpinterestlinkedinmail