Tanya Khovanova's Math Blog

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).

Recently I wrote that my blog is under attack by spam comments. Most of the comments were caught by my spam-filter Akismet, the best-known filter for WordPress. I was receiving about 50,000 comments a day and 200 of them were sneaking through this filter. I had to moderate those and delete them. This was an extreme waste of my time. But I can understand that the bots achieved some goal. None of their comments made it to my website, but at least I myself was made aware of opportunities for hair removal in Florida.

The comments crashed my server and I had to install CAPTCHAs. I was happy that the number of comments that I had to moderate went down, but the total number of comments was still so high that my server kept crashing. Now that the comments are blocked from human view, why are they still pouring in? One software package is trying to inform the other software package about weight-loss wonder drugs. I am convinced that Akismet is not interested.

My hosting provider couldn’t handle the traffic and asked me to upgrade to a more advanced hosting package. It’s annoying that I have to pay a lot of money for these bots’ attempts to sell Akismet fake Louis Vuitton bags.

The upgrade was too expensive, so I tried a different solution. I closed comments for older posts. It didn’t help. The bad software continued trying to leave comments that can’t be left. They especially like my post about Cech cycles, called A Mysterious Bracelet. My weblog tells me that every second someone downloads this page and tries to leave a comment. But no one will ever see these comments. Even Akismet will never know what it is missing: it might have had a chance to make $5,000 a day from home.

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.

The Intel International Science and Engineering Fair announced 2014 Grand Awards. I worked with three out of the top five mathematical award winners. Now I can brag that I’ve got my finger in more than half of the world’s best high-school math research.

To be clear: I wasn’t actually mentoring these projects, but I supervised two of the projects and I trained the third student for several years. So I’m proud to list the award-winning papers:

• Ritesh Ragavender got the first award for his paper Odd Dunkl Operators and nilHecke Algebras. He was our PRIMES student.
• Jesse Michel got the second award for his paper Base 1.5: Analysis of Properties and Relation to the Collatz Conjecture. He was my AMSA student for many years, although he left AMSA before he started working on this particular research project.
• Rumen Dangovski got the second award for his paper On the Lower Central Series of PI-algebras. He was our RSI student.

How interesting that each of these three students is from a different part of my present career. It certainly feels that I am in all the right places.

* * *

A mathematical tragedy: two parallel lines fall in love.

* * *

Life is not fair, even among gadgets: the desktop misbehaves, the monitor gets smacked.

* * *

An amazing magic trick! Think of a number, add 5 to it, then subtract 5. The result is the number you thought of!

* * *

—How can you distinguish a mathematician from a physicist?
—Ask for an antonym for the word parallel.
—And?
—A mathematician will answer perpendicular, and a physicist serial.

* * *

—How can you distinguish a physicist from a mathematician?
—Ask the person to walk around a post.
—And?
—A physicist will ask why, and a mathematician clockwise or counter-clockwise?

* * *

—Some bike thief managed to open my combination lock. How could they possibly guess that the combo was the year of the canonization of Saint Dominic by Pope Gregory IX at Rieti, Italy?
—What year was that?
—1234.

* * *

—Hello? Is this the anonymous FBI tip-line?
—Yes, Mr. Benson.

* * *

—My five-year-old son knows the first 20 digits of Pi.
—Wow!
— I use it as the password on my laptop, where I keep all the games.

* * *

I learned three things in school: how to rite and how to count.

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.

Let us call a natural number awesome if it can be represented as a^b + b^a, where a and b are natural numbers. For example, number 57 is awesome as 57 = 2⁵ + 5². Is 2014 awesome?

What parking spot number is the car parked in?

John Conway likes playing with the Fibonacci sequence. He invented many new sequences using the following trick. The next number in the sequence is the sum of the two previous number adjusted in some way. Free Fibonacci sequences were invented this way. Here is the recurrence for an n-free Fibonacci sequence: the next number in the sequence is the sum of the previous two numbers divided by the highest possible power of n.

Let us calculate a 2-free Fibonacci sequence starting with 5 and 4: 5, 4, 9, 13, 11, 3, 7, 5, 3, 1, 1, 1, …. I leave it to the reader to show that any 2-free sequence ends with a cycle of length one.

Let us try a 3-free Fibonacci sequence starting with 5 and 6: 5, 6, 11, 17, 28, 5, 11, 16, 1, 17, 2, 19, 7, 26, 11, 37, 16, 53, 23, 76, 11, 29, 40, 23, 7, 10, 17, 1, 2, 1, 1, 2, and so on. We are now in the cycle of length 3. Is this always the case? Not quite. If there is a 1-1-2 cycle there should be a 2-2-4 cycle, or any cycle k–k-2k, where k is coprime with 3. But the question remains: does it always end in a cycle of length 3?

I published a paper Free Fibonacci Sequences with Brandon Avila. We conjecture that a 3-free Fibonacci sequence always ends in a cycle and support this conjecture with a probabilistic argument. We were amused by how the behavior changes when we move to 4-free Fibonacci sequences. It seems that in this case sequences never cycle. We were even more amused when we moved to 5-free Fibonacci sequences and discovered that the behavior changes again.

When n equals 5 there are some sequences that cycle. Can you find the cycles? There are also sequences that grow indefinitely and we do not need a probabilistic argument to prove that. Consider Lucas numbers: 2, 1, 3, 4, 7, 11, and so on. This is a Fibonacci-like sequence that never has a term divisible by 5. Thus Lucas numbers form a 5-free Fibonacci sequence. We made a probabilistic argument that most of the starting terms converge eventually to a Lucas-like sequence that grows indefinitely because there are no terms divisible by 5.

What happens for larger n? We didn’t manage to find any cycles there. Would you like to try?