Archive for the ‘Puzzles’ Category.

I Will Be Hanged

Here is an old goodie.

Puzzle. A criminal is sentenced to death. He is offered the last word. He is allowed to make one statement. If the statement is true, the criminal will be electrocuted. If the statement is false, he will be hanged. Can you find a good piece of advice for this man?

The standard answer to this puzzle is for the criminal to say, “I will be hanged.” This creates a paradox. If he is hanged, the statement is true, and he should be electrocuted. If he is electrocuted, the statement is false, and he should be hanged.

Thinking about it, any paradox works. If the man says, “This statement is false,” then the type of punishment he gets can’t be determined.

Thinking about it some more, asking a question instead of making a statement will confuse his executioners all the same.

One of my students advised the criminal to stay silent. This was not my favorite solution, as staying silent requires some concentration. My favorite solution was the statement, “It will rain exactly a thousand years from now.” This way, the criminal can relax, at least for a thousand years.

Share:Facebooktwitterredditpinterestlinkedinmail

Scooter Ideas

Today I discuss ideas for solving the puzzle I posted previously in my blog: A Scooter Riddle.

Riddle. Alice, Bob, and Charlie are at Alice’s house. They are going to Bob’s house, which is 33 miles away. They have a 2-seat scooter that goes 25 miles per hour with 1 rider, or 20 miles per hour with 2 riders. Each of the 3 friends has a walking pace of 5 miles per hour. What is the fastest time that all three of them can end up at Bob’s house?

Let’s start.

  • The scooter and the three people should always be on the move. Moreover, whenever the scooter moves towards Bob’s house, it should carry two people, and only the driver should be on the scooter whenever it is going back.
  • We do not care about each individual’s path: whenever people meet at the same place at the same time, we can swap them. Therefore, we can assume that the scooter’s driver is the same person at all times.
  • Thinking about it, we can ignore the scooter’s driver and assume that the scooter is self-driving, and there are only two people, Alice and Bob, who need to get to Bob’s house.
  • If Alice and Bob arrive at Bob’s house at different times, there is room for improvement: the fastest person should have used the scooter less and walked more, allowing the other person more use of the scooter. Hence, we can assume that they arrive at Bob’s house simultaneously.
  • Without loss of generality, we can assume that Alice starts on the scooter first.
  • So the scooter should carry Alice for some time, drop her off, come back for Bob, then drop him off, come back for Alice, and so on. Without loss of generality, we can combine all scooter trips by the same person into one ride.
  • Thus, the plan is the following. The scooter drives Alice for x hours, drops her off, and she finishes on foot. Meanwhile, Bob starts on foot. The scooter goes back after dropping off Alice, picks up Bob, and drives him x hours the rest of the way.

Now this is just algebra. Each person covers 20x miles on the scooter and 33 − 20x miles on foot. The walking takes 33/5 − 4x hours. Thus the total trip for each person takes 33/5 − 3x hours.

Now we calculate what the scooter does. The scooter covers 20x miles with Alice and the same number of miles with Bob. It covers 40x − 33 miles alone. Thus the scooter spends 2x + (40x − 33)/25 hours in transit. The two times must be the same. So we have an equation: 6.6 − 3x = 2x + 1.6x − 1.32. Thus, x = 1.2, and the answer to the puzzle is 3 hours.


Share:Facebooktwitterredditpinterestlinkedinmail

Looking for a Well-Educated Gentleman

If you can figure out my number without the Internet, call me.

  • The number of letters in the first name of Anna Karenina’s love.
  • The number of times the word nevermore appears in the famous poem, subtracted from the month when the events took place.
  • The only number in the title of a Bergman movie.
  • The number of vowels in the original and more historically meaningful name for the sorcerer’s stone in Harry Potter books.
  • The number of vertices of the other geometric shape in “Girl on a Ball”.
  • The cube root of the age mentioned in one of the earliest Beatles songs.
  • The number corresponding to the lexicographically first string representing an integer in English.
  • The first digit of the age at which Pushkin and Mozart died.
  • The smallest of two primes such that their sum and difference are also prime.
  • The only triangular number that is also prime.

(Just in case: this is a joke and not my actual phone number.)


Share:Facebooktwitterredditpinterestlinkedinmail

My Vision for Number Gossip

I run Number Gossip, where you can input a number and get some of its cute properties. For example, the number 63 is composite, deficient, evil, lucky, and odd. In addition, it has a unique property: 63 is the smallest number out of two (the other being 69), such that the common alphabetical value of its Roman representation is equal to itself. Indeed, the Roman representation of 63 is LXIII, where L is the 12th digit, X is the 24th, and I is the 9th. Summing them up, we get 12 + 24 + 9 + 9 + 9 = 63 — the number itself.

I have a list of about 50 properties of numbers that my program checks. Each number greater than one gets at least four properties. This is because I have four groups of properties that cover all the numbers. Every number is either odd or even. Every number is either deficient, perfect, or abundant. Every number greater than one is either prime or composite. Every number is either evil or odious.

In addition, I collect unique number properties. During the website’s conception, I decided not to list all possible unique properties that I could imagine but to limit the list to interesting and unusual properties. My least favorite properties of numbers are the ones that contain many parameters. For example, 138 is the smallest number whose base 4 representation (2022) contains 1 zero and 3 twos. If you are submitting a number property to me, keep this in mind.

Some parameters are more forgiving than others. For example, 361 is the smallest number which is not a multiple of 9, whose digital sum coincides with the digital sum of its largest proper divisor. In more detail, the digital sum of 361 is 3 + 6 + 1 = 10, while 19, the largest divisor of 361, has the same digital sum of 10. In this case, the parameter 9 is special: for a multiple of 9, it is too easy to find examples that work, such as 18, 27, and so on. Sequence A345309 lists numbers whose digital sum coincides with the digital sum of their largest proper divisor. The first 15 terms of the sequence are divisible by 9, and 361 is the smallest term that is not divisible by 9.

By the way, another number that is buried deep in a sequence is 945, which is the smallest odd abundant number. There are 231 abundant numbers smaller than 945; all of them are even.

A more recent addition to my collection is related to the sequence of distended numbers (A051772). Distended numbers are positive integers n for which each divisor of n is greater than the sum of all smaller divisors. It is easy to see that for distended numbers, all sums of subsets of divisors are distinct. The opposite is not true: 175 is the smallest number, where all sums of subsets of its divisors are distinct, but the number itself is not distended.

It is difficult to find special properties for larger numbers, so I am less picky with them. For example, 3841 is the number of intersections of diagonals inside a regular icosagon. The word icosagon hides a parameter, but I still like the property.

I invite people to submit number properties to me. And I received many interesting submissions. For example, the following oxymoronic property was submitted by Alexey Radul: 1 is the only square-free square.

The numbers below 200 that still lack unique properties are 116, 147, 155, 162, 166, 182, and 194. The earliest century that doesn’t have unique number properties ranges between 7000 and 7100. The next ones are 8000–8100 and 9100–9200. By the way, my site goes up to ten thousand.

I also have a lot of properties in my internal database that I haven’t checked yet. I am most interested in the proof of the following property: 26 is the only number to be sandwiched between any two non-trivial powers.

Share:Facebooktwitterredditpinterestlinkedinmail

Best of the 2022 MIT Mystery Hunt

Every year, after the MIT Mystery Hunt was over, I would go through all the puzzles and pick out the ones related to mathematics. This year, I didn’t feel like doing it. Besides, I think it is more important to collect quality puzzles rather than all the puzzles by topic. So my new collection is the puzzles recommended to me, which I might like.

I start with math and logic puzzles.

I continue with computer science.

I carry on with some non-math fun.

I conclude with the plot device round. All the puzzles in this round are relatively easy. But our team got stuck on them until we realized that we already had the answer, which was not a single word. Here are some of the puzzles that were specifically recommended.


Crocheting Away My Pain

Share:Facebooktwitterredditpinterestlinkedinmail

Arnold’s Advice

I wrote a lot about how during entrance tests for Moscow State University, the examiners were giving Jewish and other undesirable students special (e.g. more difficult) questions during the oral exams. (See, for example, our paper Jewish Problems with Alexey Radul.) Not all examiners agreed to do this. So the administration made sure that there were different exam rooms: brutal rooms with compliant examiners torturing students with difficult questions, and normal rooms with normal examiners testing preapproved students. The administration also had other methods. One of them is the topic of this essay.

The math department of Moscow State University had four entrance exams. The first was a written math test consisting of three trivial problems, a very difficult one, and a brutally challenging one. At the end, I will show you a sample: a trivial problem and a very difficult one from 1976, my entrance year.

What was the point of such vast variation in difficulty, you may ask? There were two reasons.

But first, let me explain some entrance rules. The exam was scored according to the number of solved problems. A score of two or less was a failing score. People with such scores would be disqualified from the next exam. Any applicant with a smidge of mathematical intelligence would be able to solve all three trivial problems. Almost all applicants who qualified for the next test would have the same score of three on the first test, as they wouldn’t be able to solve the last two problems. Thus, mathematical geniuses and people who barely made the cut got the same score.

There was another rule. Officially, people with a gold medal from their high school (roughly equivalent to a valedictorian) could be accepted immediately if they scored 5 on the first exam. So one of the administrative goals was to prevent anyone getting a 5, thus, blocking Jewish applicants from sneaking in after the first exam.

Another goal was to have all vaguely qualified people get the same score. The same goal applied to other exams. After the four admission exams, the passing score, say X, was announced. A few people with a score higher than X were immediately accepted. Then there were hundreds of applicants with a score of X, way more than the quota of people the department was planning to accept. An official rule allowed the math department to pick and choose whoever they wanted from everyone who scored X.

I heard a speech by the famous Russian mathematician, Vladimir Arnold, directed at decent examiners who tested “approved” students at the oral math exam, which was the second admissions exam. His suggestion was brilliant and simple. If the students are good and belong in the department, give them an excellent grade of 5. If not, give them a failing grade of 2. Arnold’s plan boosted the chances of good students doing better than the cutoff passing score X and removed mediocre students from the competition. His idea was not only brilliant and simple but also courageous: he was risking his career by trying to fight the system.

I never experienced the entrance exams firsthand. By ministry order, as a member of the USSR IMO team, I was accepted without taking any exams. I already wrote an essay, A Hole for Jews, about how getting on the IMO team was the only way for Jewish students to get into the Moscow State University, and how the University tried to block them.

But I still looked at the entrance exam problems I would have had to solve to get in. The last two problems scared me. Now I found them again online (in Russian) at: the 1976 entrance test. The trivial problem below is standard and mechanical, while the other problem still looks scary.

Trivial problem. Solve for x:

1976 Mekhmat Entrance Test

Solution. We were drilled in school to solve these types of problems, so this one was trivial. First, make a substitution: y = 3x. This leads to an equation: (2y – 1)(y – 3)/(y2 – 2)(y – 1) ≤ 0. From this we get ranges for y: (-∞, -√2], [1/2,1], [√2, 3]. The last step is to take a logarithm.

Very difficult problem. Three spheres are tangent to plane P and to each other. Two of the spheres are the same size. The apex of a circular cone is on P, and the cone’s axis is perpendicular to the plane P. All three spheres are outside the cone and tangent to it. Find the cosine of the angle between the cone’s generatrix and the plane P, if one of the angles of the triangle formed by the intersection points of the spheres and the cone is 150 degrees.


Share:Facebooktwitterredditpinterestlinkedinmail

Already or Have

I stumbled upon one of Smullyan’s puzzle on Facebook, in Russian. I couldn’t find the original text, so I just translated it back for my students.

Puzzle. You are on an island where only truth-tellers and liars live. The truth-tellers always tell the truth, and the liars always lie. You meet an islander who sits with you for a long time, then says, “I already said this sentence.” Is he a truth-teller or a liar?

I expected the following solution. If this islander is a truth-teller, then there should have been a time when he said, for the first time, “I already said this sentence.” But this would create a contradiction.

However, my students used this puzzle as an opportunity to teach me some intricacies of the English language. They explained to me the ambiguities of my translation. Here is a shortened and lightly edited quote from one of them:

There are two different linguistic opinions that give different answers to this problem. The first is that the truth of a statement is decided at the moment it starts to be delivered: in this case, when the islander starts saying his statement. With this interpretation, for the statement to be true, he had to have said the sentence before, and for that to be true, he had to have said it even before that, and this continues indefinitely. Clearly, he cannot have been alive forever, so he has to be a liar.
The other opinion is that the verity of a statement is decided at the exact conclusion of its deliverance. Then, when the islander finishes saying his sentence, its truth is judged, and he has at that same instant “already” said the sentence, so he is telling the truth. By this interpretation, the islander is a truth-teller.

Another student had a different brilliant idea. Depending on the islander’s intonation, it is possible that he says, “I already said ‘this sentence’.” In that case, there are no self-referencing sentences, and the islander could be either a truth-teller or a liar.

I consulted my best English consultant: my son, Alexey, and here is his reply. “The basic answer is that neither truth nor semantic meaning are absolute, and edge cases will be judged differently by different observers. A sentence whose truth is time-dependent on the same scale as the duration of uttering the sentence is clearly an edge case. That’s why mathematicians intentionally try to eliminate ambiguity from their communication.”

He suggested the following fix for the puzzle’s translation.

Fixed puzzle. You meet an islander who says, “I have said this sentence before.” Is he a truth-teller or a liar?

Alexey didn’t stop at fixes and suggested the following bonus puzzles.

Bonus puzzle 1. You meet an islander who says, “I will have said this sentence.” Is he a truth-teller or a liar?

Bonus puzzle 2. You meet an islander who says, “I will say this sentence again.” Is he a truth-teller or a liar?

Share:Facebooktwitterredditpinterestlinkedinmail

The 1978 Ukrainian Math Olympiad

Ukraine is on my mind. Here is a problem for 9-graders from the 1978 Ukrainian Math Olympiad:

Problem. Prove that for every natural number n, the following number is not an integer.

1978 Ukrainian Olympiad

Share:Facebooktwitterredditpinterestlinkedinmail

Calculating the Average Age in Secret

Oskar van Deventer is a designer of beautiful mechanical puzzles. For the recent mini-MOVES gathering at the MoMath, he asked people in his Zoom breakout room to calculate the average age in the room without revealing their actual ages. I know the following solution to this puzzle.

People agree on a large number N that is guaranteed to be greater than the sum of all the ages. The first person, say Alice, thinks of a uniformly random integer R between 0 and N. Alice adds her age to R modulo N and passes the result to the second person, say Bob. Bob adds his age modulo N and passes the result to the third person, and so on. When the result comes back to Alice, she subtracts R modulo N and announces the sum total of all the ages.

During this process, no one gets any information about other people’s ages. But two people can collude to figure out the sum of the ages of the people “sitting” between them.

I gave this problem to my grandson, and he suggested the following procedure. First, people choose two trusted handlers: Alice and Bob. Then, each person splits their age into the sum of two numbers (the splitting should be random and allow one of the numbers to be negative). They then give one number to Alice and another to Bob. Alice and Bob announce the sums of the numbers they receive. After that, the sum total of everyone’s ages is the sum of the two numbers that Alice and Bob announce.

The advantage of this method is that no two people, except Alice and Bob, can collude to get more information. The disadvantage is that if Alice and Bob collude, they would know everyone’s age. Which method would you prefer?

Share:Facebooktwitterredditpinterestlinkedinmail

The Barber Paradox and English Tenses

Here is the famous barber paradox.

Paradox. The barber shaves all those and only those who don’t shave themselves. Does the barber shave himself?

If he shaves himself, then he doesn’t shave himself. If he doesn’t shave himself, then he shaves himself.

English is not my primary language, and I am fascinated by the variety of verb tenses in English as compared to the Russian language. For example, Russian has one present tense while English has four. I wonder what would happen if we use the other present tenses in this paradox.

Present continuous. The barber shaves all those and only those who aren’t shaving themselves. Does the barber shave himself?

Does this mean that the barber starts shaving himself and then has to stop, and a moment later he has to start again?

Present perfect. The barber shaves all those and only those who haven’t shaved themselves. Does the barber shave himself?

Does this mean that the barber shaves himself every other day?

Present perfect continuous. The barber shaves all those and only those who haven’t been shaving themselves. Does the barber shave himself?

Does this mean the barber shaves himself once in his lifetime and then never again?

Share:Facebooktwitterredditpinterestlinkedinmail