My Number

Here is my new logic puzzle.

I thought of a positive integer that is below 100 and is divisible by 7. In addition to the public knowledge above, I privately tell the units digit of my number to Alice and the tens digit to Bob. Alice and Bob are very logical people, but their conversation might seem strange:

Alice: You do not know Tanya’s number.
Bob: I know Tanya’s number.

What is my number?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

The Emperor and His Wizards

I recently posted a cute puzzle about the emperor and his wizards from 2015 Moscow Math Olympiad. It is time for the solution and two new variations. But first let me repeat the puzzle.

The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.

During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to discover what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.

Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.

Solution: Suppose the emperor knows one good wizard. Then he can create a chain that leads him to an evil wizard, as follows: Suppose Alice is the known good wizard. The emperor chooses some other wizard, say Bob, and asks Alice “Is Bob evil?” (which question Alice, being good, will answer truthfully). If Bob turns out to be evil, the emperor can expel him, and repeat this (starting with Alice) next round. If Bob turns out to be good, the emperor can continue, asking Bob about Carl, etc, until he either reaches an evil wizard or determines that all remaining wizards are good.

The above means that, if the emperor can find a good wizard sacrificing at most one (other) good wizard, the emperor will succeed. Here is one way to do this: Let the emperor pick Anne and ask everyone else whether Anne is good. Suppose at least one wizard, say Bill, says that Anne is good. The emperor expels Bill. If Bill is revealed to be evil, then nothing is lost, and the emperor can try again next round. If Bill is revealed to be good, then the emperor knows for sure that Anne is good and can proceed to expel all the remaining evil wizards with the chain method above. If, on the other hand, no one says that Anne is good, then the emperor expels Anne. If Anne proves evil, the emperor didn’t lose anything and can conduct another trial next round. If Anne proves good, then everyone else is evil, and the emperor can expel them all without asking any more questions.

I like the mathematical part of the puzzle, but I hate when innocent people are punished. So I couldn’t stop thinking about the puzzle until I found a variation where no good wizard need be expelled (the magic properties of the gate are redundant now, since the emperor only ever sends evil wizards through it):

The setting is the same as before, except the emperor knows how many evil wizards there are. He wants to expel all the evil wizards without expelling a good one. For which numbers of evil wizards can he do that?

In addition, my reader Leo Broukhis couldn’t get through my CAPTCHAs to post a comment (I think there’s something wrong with the plugin) but sent me a variation of the original puzzle by email:

There is again an emperor with a magic gate plagued with a superfluity of evil wizards, but this time the carnival is not very long, so the emperor does not have the luxury of asking the wizards many questions. In fact, he is restricted to asking all of them the same single question, after which he will conduct a series of expulsions that must rid the empire of evil wizards while expelling at most one good one. The one saving grace to this difficult situation is that the question need not be limited to “Yes” or “No” answers—an unbounded (single) integer is permissible.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

2015 Moscow Math Olympiad

My favorite problem at the 2015 Moscow Olympiad was about an emperor and his wizards.

8-10th grade. Designed by I.V. Mitrofanov. The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.

During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to realize what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.

Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.

Two other problems at the Olympiad were noteworthy—because no competitor solved them:

11th grade. Designed by O.N. Kosuhin. Prove that it is impossible to put the integers from 1 to 64 (using each integer once) into an 8 by 8 table so that any 2 by 2 square considered as a matrix has a determinant that is equal to 1 or −1.

9th grade. Designed by A.Y. Kanel-Belov. Do there exist two polynomials with integer coefficients such that each of them has a coefficient with absolute value exceeding 2015, but no coefficient of their product has absolute value exceeding 1?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Fear of Alzheimer

I am scared of that old German gentleman. Forgot his name. Oh, yeah. Alzheimer.

I started to lose my brain processing speed a long time ago. By my estimates I am about 100 times slower than I used to be. From time to time someone gives me a puzzle I remember I solved in 30 seconds years ago, but now it takes me 30 minutes. And it is getting worse. When I moved to my new apartment recently, it took me a year to remember my own phone number.

On the positive side, I feel quite famous, according to one of the signs of success. I am often greeted by people I don’t know.

My moment of action came when I was in my basement doing my laundry and couldn’t remember how to turn on my washing machine. This is after 10 years of heavily using this damn machine. I started to look for the button to push, but there were no buttons. There were only knobs, and I couldn’t find the word “on” anywhere. After struggling with my memory and with those knobs, I pulled out one of the knobs, and the machine started.

I panicked. I am afraid of Alzheimer’s Disease. I do not want to become demented. I do not want to forget how to count or to stop recognizing my children. I do not want to become a drain on my children’s time, emotions and money.

I had complained about my memory to my doctor before, but the only thing he ever found was anemia. This time I was more insistent. I had an MRI that ruled out tumors. I had more extensive blood tests that confirmed anemia and showed a Vitamin D deficiency. But then he sent me to a neurologist who suggested a sleep study. Finally I got a diagnosis of severe sleep apnea. I am so happy now. I might not have Alzheimer’s Disease. In the worst case scenario, I might die in my sleep. In comparison, this doesn’t sound so bad.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

A New Question about Old Coins

I want to come back to a middle-school Olympiad problem I posted a while ago.

Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times you need to weigh the coins in order to confirm that the labels are correct?

The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.

My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?

I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don’t know the answer. Can you help me?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

PRIMES Dominates High School Research

The 2015 Intel Science Talent Search results are out. This year they divided the prizes into three categories: basic research, global good, and innovation. All three top prizes in basic research were awarded to our PRIMES students:

  • First place: Noah Golowich, Resolving a Conjecture on Degree of Regularity, with some Novel Structural Results
  • Second place: Brice Huang, Monomization of Power Ideals and Generalized Parking Functions
  • Third place: Shashwat Kishore,
  • Multiplicity Space Signatures and Applications in Tensor Products of sl2 Representations

PRIMES’ success in this year’s Siemens competition is even more impressive. Unlike Intel, Siemens didn’t divide the projects into three groups. We took the first and second overall individual prizes.

  • First place: Peter Tian, Extremal Functions of Forbidden Multidimensional Matrices
  • Second place: Zoseph Zurier, Generalizations of the Joints Problem

PRIMES is the place for high school math research. Congratulations to all our students—and to me (and my colleagues) for a job well done!

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Puzzling Grades

I lead recitations for a Linear Algebra class at MIT. Sometimes my students are disappointed with their grades. The grades are based on the final score, which is calculated by the following formula: 15% for homework, 15% for each of the three midterms, and 40% for the final. After all the scores are calculated, we decide on the cutoffs for A, B, and other grades. Last semester, the first cutoff was unusually low. The top 50% got an A.

Some students who were above average on every exam assumed they would get an A, but nonetheless received a B. The average scores for the three midterm exams and for the final exam were made public, so everyone knew where they stood relative to the average.

The average scores for homework are not publicly available, but they didn’t have much relevance because everyone was close to 100%. However, a hypothetical person who is slightly above average on everything, including the homework, should not expect an A, even if half the class gets an A. There are two different effects that cause this. Can you figure them out?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

“What Does the Police Say?”

One day I received a call on my home line. I do not like calls from strangers, but the guy knew my name. So I started talking to him. I assumed that it was some official business. He told me that their company monitors Internet activities, and that my computer is emitting viruses into the Internet traffic degrading Internet performance. All I need to do is to go to my computer and he will instruct me how to get rid of my viruses.

While he was saying all this, I covered my phone’s microphone and made a call to the police from my cell phone. I was hoping the police could trace the call and do something while I kept the line to the guy open. The police told me to hang up. They said there is nothing they can do.

Meanwhile, the guy on the phone kept directing me to my Start button while I kept telling him that I can’t find it. After talking to the police, I got so angry that I told the guy that I wasn’t actually looking for the Start button, but talking to the police. So the guy asks, “What does the police say?”

These people are laughing at us. They know that the police do nothing. And then continued instructing me about my Start button.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

PamPam

Have you ever solved a CalcuDoku puzzle, or a MathDoku puzzle? Maybe you have, but you do not know it. Many incarnations of this puzzle are published under different names. The MIT’s Tech publishes it as TechDoku. What distinguishes this puzzle type from most others is that it is trademarked. The registered name is KenKen. So anyone can invent and publish a KenKen puzzle as long as they do not call it KenKen.

In this variously named puzzle you need to reconstruct a Latin square, where cells of a square are grouped into regions called cages. Each cage has a number and an operation (addition, subtraction, multiplication, division) in the upper-left corner of the cage. The operation applied to the numbers in the cage must result in a given value. For non-commutative operations (subtraction and division), the operation is applied starting from the largest number in the cage.

These are my two NOT KenKen puzzles. I will call them TomToms, the name for this puzzle used by Tom Snyder in his The Art of Puzzle LINK blog. In the TomTom variation, cages without a number in a corner are allowed and the operation might be missing, but it has to be one of the standard four. The first puzzle I call Three Threes and the second is a minimalistic version where only one number without the operation is given.

Three Threes
One Number

But my goal today is not to discuss KenKen or its ekasemans. Ekaseman is the reverse of the word namesake. My son Alexey invented the term ekaseman to denote a different name for the same thing. My real goal is to discuss a new type of puzzle that can be called Crypto KenKen. In this puzzle the digits in the corner are encrypted using a substitution cipher: each digit corresponds to its letter. I first saw this puzzle at Tom Snyder’s blog, where it is called TomTom (Cipher). I think the crypto version of this puzzle deserves its own name. So I suggest PamPam: it is an encryption of KenKen as well as TomTom. And it would be nice to have a female name for a change.

PamPam

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Laughing at 225

It is time to report on my weight loss progress. Unfortunately, the report is very boring; I am still stuck at the same weight: 225. What can I do? Let’s laugh about it. Here are some jokes on the subject.

* * *

After the holidays I stepped on my scale. After an hour I tried again and had a revelation: tears weigh nothing!

* * *

I am on a miracle diet: I eat everything and hope for a miracle.

* * *

Ideas to lose weight: A glass of water three days before your meal.

* * *

I wanted to lose five pounds by this summer, now I have only ten pounds to lose to reach my goal.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail