Archive for March 2013

My Yellow Road to Healthy Weight

Should I eat this piece of cake or not? I will certainly enjoy it very much. What harm will it do? Will this piece increase my weight? Maybe not. The next piece might, but this particular one looks harmless. Even if my weight increases by half a pound, it could be muscle weight. Yes, it probably would be due to muscle weight: I just went out of my house to throw away my garbage and this has to count as exercise.

Do you see the problem? Eating the cake provides an immediate reward, but the punishment is vague and in the far distant future. That is why I got excited when my son Alexey sent me the link to Beeminder, a company that creates an artificial non-vague and not far-in-the-future punishment for eating that piece of cake.

Here is how it works. You give them your target number — in my case my desired weight, but it could be any measurable goal — and the date by which you want to hit it. They draw a yellow path on a weight chart. You must weigh yourself every day. Whenever your weight is above your path, you have to pay real money to the company. Five dollars!

This is a great idea. Suddenly that piece of cake looks threatening. The only problem with using their system is that I have no clue how to lose weight. The company doesn’t provide tools to lose weight: it just provides a commitment device. So it is difficult to stick with the weight-loss commitment without having a proven weight-loss plan.

The truth is that my son sent me the link, I laughed, and forgot about it. Besides, if I ever want to pay money for failing in my commitments, I would rather choose the beneficiary myself. Then I realized that I can use the yellow-road idea to try to lose weight while figuring out what works for me. I call my new plan the Adaptive Diet.

Starting from my actual weight on Day One, I drew a line that represents my target weight, assuming a daily decrease of 0.1 pounds. A deviation of one pound from my target weight on my daily weigh-in is what I call my Yellow Zone. When I am in the Yellow, I continue doing what I was doing before: trying to build new, healthier habits.

If I am more than one pound below my target weight, then I have entered what I call the Green Zone. When I am in the Green, I can allow myself to indulge my cravings. However, when I am one pound above my target weight, I call that the dreaded Red Zone. This Zone has different shades of red. If I am between 1 and 2 pounds above my target weight, I have to eat only apples after 8:00pm. If I am 2 to 3 pounds above my target weight, only-apples time starts at 6:00pm. And so on. Every extra pound above my target weight moves the cut-off time by two hours. That means that if I am 7 pounds above my target weight, I would have to eat apples all day long.

The system has to work: I do not like apples.

Share:Facebooktwitterredditpinterestlinkedinmail

Skyscrapers

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.

Skyscraper Puzzle

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 fn(a, b). We will assume that a is on the left and b is on the right.

In a previous example, we showed that fn(n, 1) = 1. And of course we have fn(a, b) = fn(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, fn(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 fn(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 gn(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 gn(a) satisfies the recurrence:

Skyscraper Formula 1

Actually gn(a) is a well-known function. The numbers gn(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 fn(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 fn(1, b) = gn-1(b-1).

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

  b=2 b=3 b=4 b=5 b=6 b=7
n=2 1          
n=3 1 1        
n=4 2 3 1      
n=5 6 11 6 1    
n=6 24 50 35 10 1  
n=7 120 274 225 85 15 1

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 fn(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:

Skyscraper Formula 2

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

  b=1 b=2 b=3 b=4 b=5 b=6 b=7
a=1 0 120 274 225 85 15 1
a=2 120 548 675 340 75 6 0
a=3 274 675 510 150 15 0 0
a=4 225 340 150 20 0 0 0
a=5 85 75 15 0 0 0 0
a=6 15 6 0 0 0 0 0
a=7 1 0 0 0 0 0 0

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.

Share:Facebooktwitterredditpinterestlinkedinmail

Vampires versus Mathematicians

I just compared two searches on Google Trends:

  • How to become a vampire is in blue.
  • How to become a mathematician is in red.

Vampires versus Mathematicians

Share:Facebooktwitterredditpinterestlinkedinmail

Integers and Sequences

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 2n 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 20132013 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 p2 − 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 132013 + 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 20132013) − (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)
Share:Facebooktwitterredditpinterestlinkedinmail