Tanya Khovanova's Math Blog

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?

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.

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.

Skyscraper puzzles are one of my favorite puzzles types. Recently I discovered a new cute variation of this puzzle on the website the Art of Puzzles. But first let me remind you what the skyscraper rules are. There is an n by n square grid that needs to be filled as a Latin square: each number from 1 to n appears exactly once in each row and column. The numbers in the grid symbolize the heights of skyscrapers. The numbers outside the grid represent how many skyscrapers are seen in the corresponding columns/row from the direction of the number.

The new puzzle is called Skyscrapers (Sum), and the numbers outside the grid represent the sum of the heights of the skyscrapers you see from this direction. For example, if the row is 216354, then from the left you see 8(=2+6); and from the right you see 15(=4+5+6).

Here’s an easy Skyscrapers (Sum) puzzle I designed for practice.

The Art of Puzzles has four Skyscrapers (Sum) puzzles that are more difficult than the one above:

• Skyscrapers (Sum) by Grant Fikes
• Skyscrapers (Sum) by Thomas Snyder
• Dr. Sudoku Prescribes #146 — Skyscrapers (Sum)
• Dr. Sudoku Prescribes #69 — Skyscrapers (Sum)

I recently wrote a post about the ApSimon’s Mints problem:

New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material. Therefore, fake coins weigh the same no matter where they’ve been minted. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings in order to deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?

The post was accompanied by my paper Attacking ApSimon’s Mints.

Unfortunately, both the post and the paper contain wrong information. They both state that the number of coins as a sequence of the number of mints is 1, 2, 4, 8, 15, 38, 74. This is wrong. I took this data from the sequence A007673 in the OEIS database. The sequence had incorrect data lying dormant for 20 years. I believe that the sequence was generated from the paper of R. K. Guy and R. J. Nowakowsky, ApSimon’s Mints Problem, published in Monthly in 1994. To the credit of Guy and Nowakowsky, they never claimed to find the best solution: they just found a solution, thus providing a bound for the sequence. Someone mistook their solution for the optimal one and generated the sequence in the database.

After my post, my readers got interested in the problem and soon discovered the mistake. First Konstantin Knop found a solution for 6 mints with 30 coins and for 7 mints with 72 coins. Konstantin is my long-time collaborator. I trust him so I was sure the sequence was flawed. Then someone located a reference to a paper in Chinese A New Algorithm for ApSimon’s Mints Problem. Although none of my readers could find the paper itself nor translate the abstract from Chinese. But judging from the title and the formulae it was clear that they found better bounds than the sequence in the database. My readers got excited and tried to fix the sequence. David Reynolds improved on Konstantin’s results with a solution for 6 mints with 29 coins and for 7 mints with 52 coins. David did even better on his next try with 28 and 51 coins correspondingly. He also found a solution with 90 coins for 8 mints. Moreover, his exhaustive search proved that these were the best solutions.

Now the sequence in the database is fixed. It starts 1, 2, 4, 8, 15, 28, 51, 90.

For future generations I would like to support each number of the sequence by an example. I use the set P(Q) to represent the sequence of how many coins are taken from each mint for the first(second) weighing. For one mint, only one coin and one weighing is needed. ApSimon himself calculated the first five values, so they were not in dispute.

• a(2) = 2: P=(1,0) and Q=(0,1). Found by ApSimon.
• a(3) = 4: P=(0,1,2) and Q=(1,1,0). Found by ApSimon.
• a(4) = 8: P=(0,1,2,3) and Q=(1,0,2,2) or P=(0,1,1,4), Q=(2,0,1,1). Found by ApSimon.
• a(5) = 15: P=(0,1,1,4,5) and Q=(2,1,2,5,0). Found by ApSimon.
• a(6) = 28: P=(1,2,2,5,5,0) and Q=(0,1,2,1,8,10). Found by Robert Israel, Richard J. Mathar, and David Reynolds,
• a(7) = 51. P=(2,3,7,2,8,12,0) and Q=(0,2,1,7,7,12,12). Found by David Applegate and David Reynolds.
• a(8) = 90. P=(4,6,6,7,3,13,15,3) and Q=(4,0,1,6,12,12,1,27). Found by David Applegate and David Reynolds.

There is a solution for nine mints using 193 coins that is not confirmed to be optimal. It was found by David Reynolds: P=(1,2,4,12,5,4,20,39,43) and Q=(0,1,3,3,25,33,34,18,27). In addition, David Reynolds provided a construction that reduces the upper bound for n mints to (3⁽ⁿ⁺¹⁾−2n−3)/4. The following set of coins work: P=(1,3,7,15,…,2ⁿ−1) and Q=(1,4,13,40,…,(3ⁿ−1)/2).

I recently posted the following old Olympiad problem:

Prove that you can choose 2^k numbers from the set {1, 2, 3, …, 3^k−1} in such a way that the chosen set contains no averages of any two of its elements.

Let me show how to find 2^k − 1 such numbers. We can pick all the numbers that have 0 or 1 in their ternary representation. Let me prove that this set doesn’t contain averages. Summing two such numbers doesn’t involve carry, and the sum will contain a 1 in each place where the digits differ. On the other hand, a double of any number in this set doesn’t contain ones.

This solution is pretty, but it is not good enough: we need one more number. We can add the number 3^k−1. I will leave it to the reader to prove that the largest number in the group whose binary representation consists only of twos can be added without any harm.

There are other ways to solve this problem. It is useful to notice that multiplying a no-average set by a constant or adding a constant to it, doesn’t change the no-average property.

If we were allowed to use 0, then the problem would have been solved. As zero doesn’t belong to the initial range, we can add zero and shift everything by 1. The resulting sequence is sequence A3278. This sequence is the lexicographically first non-averaging sequence.

Another solution was suggested by devjoe in my livejournal mirror blog site. If we multiply our non-averaging set (the one that doesn’t have twos in their ternary representation) by 2, we get a set of all numbers that do not contain ones in their ternary representation. By linearity, such a set doesn’t contain averages either. We can add 1 to this set.

I recently published a crypto word search puzzle: a word search puzzle where all the letters are encrypted by a substitution cypher. The answer to such a puzzle is a word or a phrase formed by those decrypted letters that are not in the hidden words.

The puzzle I posted was easy. It can be solved by analyzing the repeated letters in the hidden words. The new puzzle is more difficult. No hidden word has repeated letters.

The hidden words are: FUN, HUNT, SOLVE, STARK, TABLE, THINK.

The puzzle below can be defined as a Crypto Word Search. Guess what needs to be done in this puzzle. The answer is a word.

The hidden words are: DUKE, EYES, RUSE, WORD, WUSS.

The idea of a crypto word search came to me from a beautiful, but devilishly difficult, puzzle In the Details, designed by Derek Kisman. In the Details can be described as a fractal word search; it contains a crypto word search as one of the simpler steps.

Here is an old Olympiad problem:

Prove that you can choose 2^k numbers from the set {1, 2, 3, …, 3^k−1} in such a way that the chosen set contains no averages of any two of its elements.

This is a variation on an old quiz. Can you answer the last question?

—An airplane carries 500 bricks. One of the bricks falls out. How many bricks are left in the airplane?
—This is easy: 499!
—Correct. Next question. How do you put a giraffe into a refrigerator?
—Open the refrigerator, put in the giraffe, and close the refrigerator door.
—Good, next. How do you put an elephant into a refrigerator?
—Open the refrigerator, take out the giraffe, put in the elephant and close the door.
—Correct. The Lion King is hosting his birthday party. All the animals come to congratulate him—except one. Why?
—The elephant couldn’t come because it is in the refrigerator.
—Fantastic, next. A man needs to cross a river inhabited by crocodiles and he doesn’t have a boat. What should he do?
—He can just swim: all the crocodiles are attending Lion King’s birthday party.
—Amazing! The last question: The man swims across the river, and dies. What happened?

Hugh ApSimon described the following coin puzzle in his book Mathematical Byways in Ayling, Beeling and Ceiling.

New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material: fake coins weigh the same independently of the mint. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings so that you can deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?

I will follow ApSimon’s notation. Suppose P_r and Q_r is the number of coins from the mint r used in the first and the second weighing correspondingly. That is, we are minimizing Σmax(P_r,Q_r). (All my summations are over all the mints. I skip the summation limits because it is difficult to write math in html.) Let us denote by W the weight of the genuine coin and by W(1 + ε) the weight of the fake coin. We do not know ε, except that it is not zero.

Let d_r be either 0 or 1, depending on what material the r-th mint uses. Thus, the coin from the r-th mint weighs W(1 + d_rε). We know the results of these two weighings and the weight of the genuine coin. Therefore, we can calculate the following two values: a = ΣP_rd_rε and b = ΣQ_rd_rε.

It is clear that we need to request at least one coin from each mint and use it in at least one weighing: P_r + Q_r > 0. If both sums a and b are zero, then all the mints are producing genuine coins. Neither of the two values gives us much information as we do not know ε. We can get rid of ε by dividing a by b.

There are 2ⁿ − 1 combinations of possible answers: these are subsets of the set of mints producing fake coins given that there is at least one. Thus we need to select numbers P_r and Q_r, so that a/b produces 2ⁿ − 1 possible answers for different sets of values of d_r.

Let us consider cases in which the total number of mints is small. If there is one mint we can take one coin and we won’t even need a second weighing. For two mints we need one coin from each mint for a total of 2. For three mints, one coin from each mint is not enough. I leave this statement as an exercise. It is possible to test three mints with four coins: one each from the first and second mints and two from the third mint. The coins from each mint for the first and second weighings are (0,1,2) and (1,1,0) respectively.

To prove that this works we need to calculate (d₂ + 2d₃)/(d₁ + d₂) for seven different combinations of d_r. I leave this as an exercise.

This puzzle seems to be very difficult. We only know the answer if the number of mints is not more than seven. The corresponding sequence A007673 in the OEIS is: 1, 2, 4, 8, 15, 38, 74. It is possible to give bounds for this sequence, but they are so far apart. The lower bound is n. And the ApSimon’s book offers a construction for two weighings were P_r = r! and Q_r = 1.

You can try to find a better construction, or you can try calculating more terms of the sequence. You can also read more about this problem in my short paper Attacking ApSimon’s Mints.

I do not want to leave the readers with the puzzle that might end up being intractable. So I suggest the following easy puzzle. Solve the ApSimon’s Mints problem assuming that the weight of the fake coin is known.