Tanya Khovanova's Math Blog

I recently posted the following problem from the Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

• Prove that all the people have exactly the same number of acquaintances at this meeting.
• Show that n can be greater than 4.

Here is the proof for the first bullet. Choose a person X. Take a pair of X‘s acquaintances. These two acquaintances have to share two acquaintances between themselves one of whom is X. In other words, we have described a function from all pairs of X‘s acquaintances to people who are not X. On the other hand, for every person who is not X, s/he and X share a pair of acquaintances. Hence, there is a bijection between people other than X and all pairs of X‘s acquaintances. If the number of X‘s acquaintances is a, and the total number of people is t, then we have shown that (a choose 2) = t−1. As this is true for any X, we see that everyone has the same number of acquaintances. Moreover, this situation can happen only if t−1 is a triangular number.

But wait. There is more work that needs to be done. The smallest triangular number is 1. That means that t might be 2. If there are two people at the meeting, then the condition holds: they have 0 common acquaintances. The next triangular number is 3. So we need to see what would happen if there are four people. In this case, if everyone knows each other, it works. This is why the second bullet asks us to find an example of the situation with more than four people, because four people is too easy.

Let’s look at larger triangular numbers. The situation described in the problem might also happen when there are:

• 7 people total and everyone has 4 acquaintances,
• 11 people total and everyone has 5 acquaintances,
• 16 people total and everyone has 6 acquaintances,
• and so on: a(a−1)/2 + 1 people total and everyone has a acquaintances.

The official Olympiad solution suggests the following example for 16 people total. Suppose we put 16 people in a square formation so that everyone knows people in the same row and column. I leave it to the reader to check that every two people share exactly two acquaintances.

Let me prove that there is no solution for a total of seven people. If there were a solution, then each person would have to know four people. My first claim is that the acquaintance graph can’t contain a four-clique. Suppose there is a four-clique. Then each person in the clique has to have another acquaintance outside of the clique to make it up to four. In addition, this extra acquaintance can’t be shared with anyone in the clique, because the clique contains all the acquaintances that they share. This means we need to have at least four more people.

Next, suppose two people a and b know each other and share an acquaintance c. Any two people in this group of three has to have another shared acquaintance, who is not shared with the third person. That is, there should be another person who is the acquaintance of a and b, a different person who is an acquaintance of a and c, and a third person who is acquainted with b and c. These three extra people are all the acquaintances of a, b, and c. Which means the last person who is not acquainted with a, b, or c, has less than for four acquaintances.

Let’s look at a more difficult problem that I offered at the same posting:

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

• Prove that all the people have exactly the same number of acquaintances at this meeting.
• Is it possible that n can be greater than 2k?

As in the previous solution, we see that a, the number of acquaintances of a person and t, the total number of people, satisfy the following equation: (a choose k) = (t−1 choose k−1).

For example, if k = 3, the equation becomes (a choose 3) = (t−1 choose 2). This is a question of finding numbers that are both tetrahedral and triangular. They are known and their sequence, A027568, is finite: 0, 1, 10, 120, 1540, 7140. The corresponding number of acquaintances is 3, 5, 10, 22, 36 and the total number of people is 3, 6, 17, 57, 121. The first trivial example involves 3 people who do not know each other. The next example is also simple: it has 6 people and everyone knows everyone else.

What about non-trivial examples? If there are 17 people in the group, then each person has to know 10 people. Does the acquaintance graph exist so that every group of three people share 3 acquaintances?

We see that the problem consists of two different parts. First, we have to solve the equation that equates two binomial coefficients. And second, we need to build the acquaintance graph. Both questions are difficult. We see that for k = 2 we have an infinite number of solutions to the equation with binomial coefficients. For k = 3, that number is finite. What happens with other k? If there are 2k people and they all know each other, then this works. But are there other non-trivial solutions? I am grateful to Henry Cohn for directing me to the works of Singmaster who studied non-trivial repetitions of numbers in Pascal’s triangle. In particular, Singmaster showed that the equation (n+1 choose k+1) = (n choose k+2) has infinitely many solutions given by n = F_2i+2F_2i+3−1 and k = F_2iF_2i+2−1.

This sequence generates the following non-trivial examples (15 choose 5) = (14 choose 6), (104 choose 39) = (103 choose 40), and so on. That means it might be possible that there is a group of 16 people so that every 6 people share 6 acquaintances. In this situation every person must know everyone else except for one other person. That leads us to the structure of the acquaintance graph: it is a complement to the perfect matching graph. I leave it to my readers to check that the corresponding acquaintance graph doesn’t exist. Are there examples of two binomial coefficients that equal each other and that lead to an acquaintance graph that can be built?

Now that I’ve tackled the solution to this Olympiad problem, I see that I generated more questions than I answered.

I recently published the following coin puzzle:

There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

My readers, David Reynolds and ext_1973756, wrote to me that I am missing a coin of 4 grams. Indeed, the same puzzle with five coins—1, 2, 3, 4, and 5—is a more natural and a better puzzle.

David Reynolds also suggested to go all the way up to 9 coins:

There are nine silver coins marked 1, 2, 3, 4, 5, 6, 7, 8, and 9. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

It is impossible to resolve this situation with more than nine coins as two weighings provide nine different answers to differentiate coins. But indeed it is possible to solve this problem for nine coins. It is even possible to suggest a non-adaptive algorithm, that is to describe the weighings before knowing the results.

To find such a strategy we need to satisfy two conditions. First, we have to weigh groups of coins of the same supposed weight, otherwise we do not get any useful information. Second, there shouldn’t be any two coins together (in or out of the pan) in both weighings, because it would then be impossible to differentiate between them.

Here is one possible solution of the problem:

• The first weighing: 1, 5, and 9, against 2, 6, and 7
• The second weighing: 1, 6, and 8, against 2, 4, and 9

David Reynolds also suggested a problem in which we do not know whether the fake coin is heavier or lighter:

There are four silver coins marked 1, 2, 3, and 4. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

Again, four coins is the best we can do when in addition to find it, we also want to determine if it is heavier or lighter. Indeed, if there were five coins we would have needed to cover ten different answers, which is too many for two weighings.

Here is the solution for four coins:

The two weighings are 1+3=4, and 1+2=3. If the first weighing balances, then the fake coin is 2 and the second weighing shows if it is heavier or lighter than it should be. Similarly, if the second weighing balances, then the fake coin is four and we can see whether it is heavier or lighter than it should be. If the left pan is lighter/heavier for both weighings, then the fake coin is 1 and is lighter/heavier. But if one pan is heavier on the first of two weighings and the other pan is heavier on the second weighing, then the fake coin is 3. In both cases it is easy to determine whether the fake coin is heavier or lighter.

Now David is missing a coin. If we just want to find the fake coin without determining whether it is heavier of lighter, we can do it with five coins:

There are five silver coins marked 1, 2, 3, 4, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

We can use the same solution as the previous (four coins) problem. If the scale balances both times, then the fake coin is 5. However, in this case we will not know whether the coin is heavier or lighter.

We can’t extend this problem to beyond five coins. Suppose we have six coins. We can’t use more than three coins in the first weighing. This is because if the scale unbalances, we can’t resolve more than three coins in one remaining weighing. Suppose the first weighing balances; then we have at least three leftover coins we know nothing about and one of them is fake. These three coins should be separated for the next weighing. That means one of the coins needs to be on the left pan and one on the right pan. We can add real coins any way we need. But if the second weighing unbalances we do not know if the fake coin is on the left and lighter or on the right and heavier.

My new favorite hat puzzle was invented by Konstantin Knop and Alexander Shapovalov. It appeared (in a different wording) in March 2013 at the Tournament of the Towns:

A sultan decides to give 100 of his sages a test. The sages will stand in line, one behind the other, so that the last person in the line sees everyone else. The sultan has 101 hats, each of a different color, and the sages know all the colors. The sultan puts all but one of the hats on the sages. The sages can only see the colors of the hats on 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. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get 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?

I loved it so much that I wrote a paper about it. You can find the solution there.

I particularly like these two problems that I gave my AMSA students for homework:

Athos, Porthos, and Aramis were rewarded with six coins: three gold and three silver. Each got two coins. Athos doesn’t know what kind of coins the others got, but he knows his own coins. Ask him one question to which he can answer “Yes,” “No,” or “I do not know,” so that you will be able to figure out his coins.

There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

We’ve all been hearing about parallel computing, and now it has turned up in a coin-weighing puzzle invented by Konstantin Knop.

“We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter, but all genuine coins weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts a minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?”

This puzzle reminds me of another coin-weighing problem, where in a similar situation you need to find a fake coin by using one scale with four pans. The answer in this variation would be 5⁵ = 3125. We can divide coins in five groups with the same number of coins and put four groups on the scale. If one of the groups is different (heavier or lighter), then this group contains the fake coin. Otherwise, the leftover group contains the fake coin. This way each weighing reduces the pile with the fake coin by a factor of five. One scale with four pans gives you more information than two scales with two pans used in parallel. We can conclude that Knop’s puzzle should require at least the same number of weighings as the four-pan puzzle for the same number of coins. So we can expect the answer to Knop’s puzzle will not be bigger than 3125. But what will it be?

Here is a problem from the 2012 Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

• Prove that all the people have exactly the same number of common acquaintances at this meeting.
• Show that n can be greater than 4.

My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.

Let’s take this up a notch and work on a more difficult problem.

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

• Prove that all the people have exactly the same number of common acquaintances at this meeting.
• Is it possible that n can be greater than 2k?

This is the promised solution to the puzzle Integers and Sequences that I posted earlier. The puzzle is attached below.

Today I do not want to discuss the underlying math; I just want to discuss the puzzle structure. I’ll assume that you solved all the individual clues and got the following lists of numbers.

• 12 42 18 40 30 24 20
• 2 1 132 42 429 14
• 7 9 1 8 5 3 10 4
• 92 117 70 145 35 1 22 12 5
• 137 1 37 13 107 1013 113
• 30 12 2 42 6
• 70 4030 836 7192

Since the title mentions sequences, it is a good idea to plug the numbers into the Online Encyclopedia of Integer Sequences. Here is what you will get:

• not clear
• Catalan numbers with 5 missing: 1, 1, 2, 5, 14, 42, 132, 429
• not clear
• Pentagonal numbers with 51 missing: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145
• Primeval numbers with 2 missing: 1, 2, 13, 37, 107, 113, 137, 1013
• not clear
• Weird numbers with 5830 missing: 70, 836, 4030, 5830, 7192

Your first “aha moment” happens when you notice that the sequences are in alphabetical order and each has exactly one number missing. The alphabetical order is a good sign that you are on the right track; it can also narrow down the possible names of the sequences that you haven’t yet identified. Alphabetical order means that you have to figure out the correct order for producing the answer.

Did you notice that some groups above are as long as nine integers and some are as short as four? In puzzles, there is nothing random, so the lengths of the groups should mean something. Your second “aha moment” will come when you realize that, together with the missing number, the number of the integers in each group is the same as the number of letters in the name of the sequence. This means you can get a letter by indexing the index of the missing number into the name of the sequence.

So each group of numbers provides a letter. Now we need to identify the remaining sequences and figure out in which order the groups will produce the word that is the answer.

Let’s go back and try to identify the remaining sequences. We already know the number of letters in the name of each sequence, as well as the range within the alphabet. The third sequence might represent a challenge as its numbers are small and there might be many sequences that fit the pattern, but let’s try. The results are below with the capitalized letter being the one that is needed for the answer.

• abundAnt
• caTalan
• dEficient or iMperfect
• pentaGonal
• pRimeval
• proNic or proMic
• weiRd

What is going on? There are two sequences that fit the pattern of the third group and the sequence for the sixth group has many names, two of which fit the profile but produce different letters. Now we get to your third “aha moment”: you have already seen some of the sequence names before, because they are in the puzzle. This will allow you to disambiguate the names.

Now that we have all the letters, we need the order. Sequences are mentioned inside the puzzle. You were forced to notice that because you needed the names for disambiguation. Maybe there is something else there. On closer examination, all but one of the sequence names are mentioned. Moreover, with one exception the clues for one sequence mention exactly one other sequence. Once you connect the dots, you’ll have your last “aha moment:” the way the sequences are mentioned can provide the order. The first letter G will be from the pentagonal sequence, which was not mentioned. The clues for the pentagonal sequence mention the primeval sequence, which will give the second letter R, and so on.

The answer is GRANTER.

Many old-timers criticized the 2013 MIT Mystery Hunt. They are convinced that a puzzle shouldn’t have more than one “aha moment.” I like my “aha moments.”

*****

• (the largest integer n such that there exists a Platonic solid with n vertices, a Platonic solid with n edges, and a Platonic solid with n faces)
• (the largest two-digit tetrahedral number)/(the smallest value the second smallest angle of a convex hexagon with all integer degrees can have)
• (the number of positive integers less than 2013 that are divisible by 100, but not divisible by 70)
• (the number of two-digit numbers that produce a square when summed up with their reverse) ⋅ (the smallest number of weighings on a balance scale that guarantees to find the only fake coin out of 100 identical coins, where the fake coin is lighter than other coins)
• (the only two digit number n such that 2ⁿ ends with n) − (the second smallest, and conjectured to be the largest, triangular number such that its square is also triangular)
• (the smallest non-trivial compositorial number that is also a factorial)
• (the sum of the smallest three positive pronic numbers)

*****

• (the digit you get when you sum up the digits of 2013²⁰¹³ repeatedly until you get a single digit) − (the greatest common factor of the indices of the Fibonacci numbers divisible by 13)
• (the largest common divisor of numbers of the form p² − 1 for primes p greater than three) − (the largest sum of digits that can appear on a 12-hour digital clock starting from 1:00 up to 12:59)
• (the largest Fibonacci number, such that it and all positive Fibonacci numbers less than it are deficient) + (the difference between the sum of all even numbers up to 100 and the sum of all odd numbers up to 100) − (the first digit of a four-digit square that has the first two digits the same and the last two digits the same)
• (the smallest composite Jacobsthal number) ⋅ (the only digit needed to express the number of diagonals of a convex hendecagon)/(the smallest prime divisor of 13²⁰¹³ + 1)
• (the smallest integer the fate of whose aliquot sequence is unknown) + (the largest amount of money in cents you can have in American coins without having change for 2 dollars) − (the repeated number in the aliquot cycle of 95) ⋅ (the second-smallest integer n such that the Russian word for n has n letters)
• (the smallest positive even integer that’s not a totient)

*****

• (the number of letters in the last name of a famous Russian writer whose year of birth many Russians use to help them memorize the digits of e)
• (the number of pluses you need to insert in a row of 20 fives so that the sum is 1000)
• (the number of positive integers less than 2013 such that not all their digits are distinct) − (the number of four-digit numbers with only odd digits) − (the largest Fibonacci square)
• (the number of positive integers n for which the sum of the n smallest positive integers evenly divides 18n)
• (the number of trailing zeroes of 2013!) − (the number of sets in the game of Set such that every feature is different on all three cards) − (an average speed in miles per hour of a person who drives somewhere with a speed of 420 miles per hour, then drives back using the same route with a speed of 210 miles per hour)
• (the smallest fortunate triangular number)
• (the smallest weird number)/(the only prime one less than a cube)
• (the third most probable product of the numbers showing when two standard six-sided dice are rolled)

*****

• (the largest integer number of dollars you can’t pay if you have an unlimited supply of 9-dollar bills and 13-dollar bills) − (the positive difference between the two prime numbers that do not share a unit digit with any other prime number)
• (the largest three-digit primeval number) − (the largest number of distinct SET cards without a set)
• (the number conjectured to be the second-largest number such that two to its power has no zeroes) − (the largest number whose cube has at most two distinct digits and no zeroes)
• (the number of 5-digit palindromic integers in base 5) + (the only positive integer that is five times the sum of its digits)
• (the only Fibonacci number that is a double of a prime) + (the only prime p such that p! has p digits) − (the only fixed point of look-and-say operation)
• (the only number whose concatenation with itself is prime)
• (the only positive integer that that differs by 1 from a square and a nonsquare cube) − (the largest number such that its divisors are each 1 less than a prime)
• (the smallest admirable number)
• (the smallest evil untouchable number)

*****

• (the alphanumeric value of MANIC SAGES) + (the sum of all three-digit numbers you can get by permuting digits 1, 2, and 3) + (the number of two-digit integers divisible by 9) − (the number of rectangles whose sides are composed of edges of squares of a chess board)
• (the integer whose standard Roman numeral representation is alphabetically later than all others) − (the number you get if you divide a three digit number with identical digits by the sum of the digits)
• (the largest even integer that is not a sum of two abundant numbers) − (the digit in the first position where e and π have the same digit)
• (the number formed by the last two digits of the sum: 1! + 2! + 3! + 4! + . . . + 2013!)
• (the only positive integer such that if you sum the digits and the squares of the digits, you get the original number back) + (the largest prime factor of the smallest Carmichael number)
• (the smallest multi-digit hyperperfect number such that more than half of its digits are the same) − (the sum of digits that cannot be the last digits of squares) ⋅ (the largest base n in which 8n is not written like 80) ⋅ (the smallest positive integer that leaves a remainder of 2 when divided by 3, 4, and 5)
• (the smallest three-digit brilliant number) − (the first decimal digit of the number that in hexadecimal gives the house number of Sherlock Holmes)

*****

• (the number of evil minutes in an hour)
• (the number of fingers on ten hands) − (the smallest number such that its square has a digit repeated three times)
• (the number of ways you can rearrange letters of MANIC)/(the number of ways you can rearrange letters of SAGES)
• (the only multi-digit Catalan number with digits in strictly decreasing order)
• (the smallest perfect number)

*****

• (the largest product of positive integers that sum up to 10) + (the smallest perimeter of a rectangle with integral sides of area 120) − (the day of the month of the second Thursday in a January that has exactly 4 Mondays and 4 Fridays)
• (the second-largest number with all distinct digits, such that all the words in its American English representation start with the same letter) + (the largest square-free composite number that contains each of the digits 1, 2, 3, 4 exactly once in its prime factorization) + (the number of ways you can flip a coin 10 times so that the number of heads is the same as the number of tails) + (the smallest positive integer such that 2 to its power contains 2013 as a substring) + (the sum of five prime numbers formed from the digits 2, 3, 5, 7, 8, 9 where each digit is used exactly once) + (the number of days in a year where the day of the month is odious) + (the sum of the digits each of which spelled out has an alphanumeric value equal to the meaning of life, the universe, and everything) ⋅ (the sum of all prime numbers p such that p + 20 and p + 40 are also prime) + (the first digit of the total number of legal moves of the Black king in chess)
• (the second-largest three-letter palindrome in Roman numerals)/((the smallest composite number not divisible by any of its digits)/(the last digit of 2013²⁰¹³) − (the digit in position 2013 of the string formed by concatenation of all integers into one stream: 123456789101112…)) − (the number of days in a year such that the month and the day of the month are simultaneously composite)
• (the second-smallest cube with only prime digits) ⋅ (the smallest perimeter of a Pythagorean triangle)/(the last digit to appear in the units place of a Fibonacci number) + (the greatest common divisor of the sums in degrees of the interior angles of convex polygons with an even number of sides) + (the number of subsets that you can form from the set {1,2,3,4,5,6,7,8,9} that do not contain two consecutive numbers) − (the only common digit of 2013 base 8 and base 9)

Tanya Khovanova and Joel Brewster Lewis

In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).

In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.

Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.

Let’s continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.

Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let’s denote the total number of permutations by f_n(a, b). We will assume that a is on the left and b is on the right.

In a previous example, we showed that f_n(n, 1) = 1. And of course we have f_n(a, b) = f_n(b, a).

Let’s discuss a couple of other examples.

First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, f_n(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.

Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case f_n(a,n+1-a) is (n-1) choose (a-1). Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a-1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.

Before going further let us see what happens if only one of the maxima is given. Let us denote by g_n(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a-1 of them. If the shortest building is not on the left, then it can be in any of the n-1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function g_n(a) satisfies the recurrence:

Actually g_n(a) is a well-known function. The numbers g_n(a) are called unsigned Stirling numbers of the first kind (see https://oeis.org/A132393); not only do they count permutations with a given number of left-to-right (or right-to-left) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)…(x + n), among other places. (Another pair of exercises.)

We are now equipped to calculate f_n(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b-1 more buildings are seen from the right. That is f_n(1, b) = g_n-1(b-1).

Here is the table of non-zero values of f_n(1, b).

Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. We can take any permutation counted by f_n(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n-1, the first k values form a permutation with a – 1 left-to-right maxima and the last n – k – 1 values form a permutation with b – 1 right-to-left maxima, and there are no other restrictions. Thus:

Let’s have a table for f₇(a,b), of which we already calculated the first row:

We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).

The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.

The most personal puzzle that I wrote for the 2013 MIT Mystery Hunt was Integers and Sequences based on my Number Gossip database. I named it after the first lecture that I prepared after I decided to return to mathematics. It is still my most popular lecture.

Many of the clues in this puzzle are standard math problems that are very good for math competition training. Other clues are related to sequences and integer properties.

You might wonder why I often ask for the second largest integer with some property. Isn’t the largest one more interesting than the second largest? I do think that the largest number is more interesting, but exactly for this reason the largest number is available on my Number Gossip website and therefore is googleable. For example, my Number Gossip properties for 3000 contain the fact that 3000 is the largest palindrome in Roman numerals. This is why in the puzzle I used a slightly different clue, i.e. “the second largest three-letter palindrome in Roman numerals.”

It took me many hours to find non-googleable variations of interesting properties for this puzzle. Unfortunately, its non-googleability evaporated as soon as my solution was posted, right after the hunt. In any case some clues in this puzzle are useful for math competition training, and I plan to use them myself in my classes. The puzzle is attached below. I will post the solution in a couple of weeks.

*****

• (the largest integer n such that there exists a Platonic solid with n vertices, a Platonic solid with n edges, and a Platonic solid with n faces)
• (the largest two-digit tetrahedral number)/(the smallest value the second smallest angle of a convex hexagon with all integer degrees can have)
• (the number of positive integers less than 2013 that are divisible by 100, but not divisible by 70)
• (the number of two-digit numbers that produce a square when summed up with their reverse) ⋅ (the smallest number of weighings on a balance scale that guarantees to find the only fake coin out of 100 identical coins, where the fake coin is lighter than other coins)
• (the only two digit number n such that 2ⁿ ends with n) − (the second smallest, and conjectured to be the largest, triangular number such that its square is also triangular)
• (the smallest non-trivial compositorial number that is also a factorial)
• (the sum of the smallest three positive pronic numbers)

*****

• (the digit you get when you sum up the digits of 2013²⁰¹³ repeatedly until you get a single digit) − (the greatest common factor of the indices of the Fibonacci numbers divisible by 13)
• (the largest common divisor of numbers of the form p² − 1 for primes p greater than three) − (the largest sum of digits that can appear on a 12-hour digital clock starting from 1:00 up to 12:59)
• (the largest Fibonacci number, such that it and all positive Fibonacci numbers less than it are deficient) + (the difference between the sum of all even numbers up to 100 and the sum of all odd numbers up to 100) − (the first digit of a four-digit square that has the first two digits the same and the last two digits the same)
• (the smallest composite Jacobsthal number) ⋅ (the only digit needed to express the number of diagonals of a convex hendecagon)/(the smallest prime divisor of 13²⁰¹³ + 1)
• (the smallest integer the fate of whose aliquot sequence is unknown) + (the largest amount of money in cents you can have in American coins without having change for 2 dollars) − (the repeated number in the aliquot cycle of 95) ⋅ (the second-smallest integer n such that the Russian word for n has n letters)
• (the smallest positive even integer that’s not a totient)

*****

• (the number of letters in the last name of a famous Russian writer whose year of birth many Russians use to help them memorize the digits of e)
• (the number of pluses you need to insert in a row of 20 fives so that the sum is 1000)
• (the number of positive integers less than 2013 such that not all their digits are distinct) − (the number of four-digit numbers with only odd digits) − (the largest Fibonacci square)
• (the number of positive integers n for which the sum of the n smallest positive integers evenly divides 18n)
• (the number of trailing zeroes of 2013!) − (the number of sets in the game of Set such that every feature is different on all three cards) − (an average speed in miles per hour of a person who drives somewhere with a speed of 420 miles per hour, then drives back using the same route with a speed of 210 miles per hour)
• (the smallest fortunate triangular number)
• (the smallest weird number)/(the only prime one less than a cube)
• (the third most probable product of the numbers showing when two standard six-sided dice are rolled)

*****

• (the largest integer number of dollars you can’t pay if you have an unlimited supply of 9-dollar bills and 13-dollar bills) − (the positive difference between the two prime numbers that do not share a unit digit with any other prime number)
• (the largest three-digit primeval number) − (the largest number of distinct SET cards without a set)
• (the number conjectured to be the second-largest number such that two to its power has no zeroes) − (the largest number whose cube has at most two distinct digits and no zeroes)
• (the number of 5-digit palindromic integers in base 5) + (the only positive integer that is five times the sum of its digits)
• (the only Fibonacci number that is a double of a prime) + (the only prime p such that p! has p digits) − (the only fixed point of look-and-say operation)
• (the only number whose concatenation with itself is prime)
• (the only positive integer that that differs by 1 from a square and a nonsquare cube) − (the largest number such that its divisors are each 1 less than a prime)
• (the smallest admirable number)
• (the smallest evil untouchable number)

*****

• (the alphanumeric value of MANIC SAGES) + (the sum of all three-digit numbers you can get by permuting digits 1, 2, and 3) + (the number of two-digit integers divisible by 9) − (the number of rectangles whose sides are composed of edges of squares of a chess board)
• (the integer whose standard Roman numeral representation is alphabetically later than all others) − (the number you get if you divide a three digit number with identical digits by the sum of the digits)
• (the largest even integer that is not a sum of two abundant numbers) − (the digit in the first position where e and π have the same digit)
• (the number formed by the last two digits of the sum: 1! + 2! + 3! + 4! + . . . + 2013!)
• (the only positive integer such that if you sum the digits and the squares of the digits, you get the original number back) + (the largest prime factor of the smallest Carmichael number)
• (the smallest multi-digit hyperperfect number such that more than half of its digits are the same) − (the sum of digits that cannot be the last digits of squares) ⋅ (the largest base n in which 8n is not written like 80) ⋅ (the smallest positive integer that leaves a remainder of 2 when divided by 3, 4, and 5)
• (the smallest three-digit brilliant number) − (the first decimal digit of the number that in hexadecimal gives the house number of Sherlock Holmes)

*****

• (the number of evil minutes in an hour)
• (the number of fingers on ten hands) − (the smallest number such that its square has a digit repeated three times)
• (the number of ways you can rearrange letters of MANIC)/(the number of ways you can rearrange letters of SAGES)
• (the only multi-digit Catalan number with digits in strictly decreasing order)
• (the smallest perfect number)

*****

• (the largest product of positive integers that sum up to 10) + (the smallest perimeter of a rectangle with integral sides of area 120) − (the day of the month of the second Thursday in a January that has exactly 4 Mondays and 4 Fridays)
• (the second-largest number with all distinct digits, such that all the words in its American English representation start with the same letter) + (the largest square-free composite number that contains each of the digits 1, 2, 3, 4 exactly once in its prime factorization) + (the number of ways you can flip a coin 10 times so that the number of heads is the same as the number of tails) + (the smallest positive integer such that 2 to its power contains 2013 as a substring) + (the sum of five prime numbers formed from the digits 2, 3, 5, 7, 8, 9 where each digit is used exactly once) + (the number of days in a year where the day of the month is odious) + (the sum of the digits each of which spelled out has an alphanumeric value equal to the meaning of life, the universe, and everything) ⋅ (the sum of all prime numbers p such that p + 20 and p + 40 are also prime) + (the first digit of the total number of legal moves of the Black king in chess)
• (the second-largest three-letter palindrome in Roman numerals)/((the smallest composite number not divisible by any of its digits)/(the last digit of 2013²⁰¹³) − (the digit in position 2013 of the string formed by concatenation of all integers into one stream: 123456789101112…)) − (the number of days in a year such that the month and the day of the month are simultaneously composite)
• (the second-smallest cube with only prime digits) ⋅ (the smallest perimeter of a Pythagorean triangle)/(the last digit to appear in the units place of a Fibonacci number) + (the greatest common divisor of the sums in degrees of the interior angles of convex polygons with an even number of sides) + (the number of subsets that you can form from the set {1,2,3,4,5,6,7,8,9} that do not contain two consecutive numbers) − (the only common digit of 2013 base 8 and base 9)

The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:

There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.

Actually, it is possible to find the real coin in six weighings. Can you do that?