Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
17 December 1999

Millennium Magic

I think of the Y2K New Year as an odometer day, when digits reset to zero. It's just a number thing, so here's another. Circle any number on the grid below, and then cross out all the other numbers in its row and column. Now circle any remaining number and cross out all the others in its row and column. Do it again, and again, and then circle that last remaining number. The sum of your five circled numbers will always be 1,999! Can you make your own magic grid that adds up to 2000 for the new year? How does this work? How many solutions are there?

  296     456     319     287     324  
  452     612     475     443     480  
  313     473     336     304     341  
  420     580     443     411     448  
  316     476     339     307     344  

When you're done the grid might look like this,
though you'll probably select different numbers:

420 + 473 + 475 + 307 + 324 = 1,999

I made the Y2K grid below by adding one to each number in the center column of the 1999 grid. You can add one to any row or column for the same result. This number square is really just an addition table for the hidden numbers shown in yellow around the outside of the grid. The special way of picking 5 numbers guarantees that each row and column is selected just once. So the magic sum must be the sum of these 10 outside numbers. How many Y2K grids are possible? Well, how many ways are there to add 10 numbers and get 2000? Lots!

420 + 473 + 476 + 307 + 324 = 2,000
because
(411 + 9) + (304 + 169) + (443 + 33) + (307 + 0) + (287 + 37) = 2,000

Notes:

I like how this stumper seems so mysterious at first, and so obvious once you see how it works. It's easy to make your own magic grids for any number. You can make interesting birthday cards this way!

  1. Pick the magic sum and the size of the square grid.
  2. For a grid of size n, find 2n numbers that add up to the desired sum.
  3. Build the matrix as an addition table by adding the row and column numbers for each square.
That's it! The grid must be square, but there are no other restrictions. Negative numbers, decimals, and fractions work just fine. Numbers don't have to be unique, but it's more interesting if they are to avoid duplicate rows and columns.

Graybear got this stumper right off:

The easiest way to make a grid that adds to 2000 is to pick a row OR column at random and add 1 to each value in that row or column. This works because, no matter how you choose, each row/column supplies one of the five values to be added together. Now that we have established the logic, we see that we can create another grid that 'adds' to 2000 by selecting 10 numbers that add to 2000, assigning each of those numbers to a row or a column, and then filling each square of the grid by adding its row and column values. The number of unique grids is where we will have some fun with this stumper...
Indeed. But trying to find the exact answer put me in over my head with some difficult math.

How many ways are there to find 10 numbers that add up to 2000? The answer is some degree of infinity if we allow decimals or fractions or negative numbers, but there's a definate answer if we only consider positive integers. This problem is a bit like factoring into primes, but different, and harder.

The exact answer is P(2000,10) if we allow numbers to repeat, and Q(2000,10) with the constraint that all numbers are different.

P( ) and Q( ) are Partition Functions as defined in number theory:

For example, consider P(6):

(1) 6    =    6
(2)   = 5 + 1
(3)   = 4 + 2
(4)   = 4 + 1 + 1
(5)   = 3 + 3
(6)   = 3 + 2 + 1
(7)   = 3 + 1 + 1 + 1
(8)   = 2 + 2 + 2
(9)   = 2 + 2 + 1 + 1
(10)   = 2 + 1 + 1 + 1 + 1
(11)   = 1 + 1 + 1 + 1 + 1 + 1

From this partitioning, we see that:

P(6) = 11 {1 .. 11}(all partitions)
Q(6) = 4 {1, 2, 3, 6}(all partitions with unique numbers)
P(6,2) = 3 {2, 3, 5}(all partitions into 2 numbers)
Q(6,2) = 2 {2, 3}(all partitions into 2 unique numbers)

This is easy with small numbers, but P( ) and Q( ) are eponential functions that grow large fast!

The following table from Eric Weisstein's World of Mathematics site gives the exact value of P(n) for some larger values of n:

n   P(n)    
50   204,226   2 x 10 5
100   190,569,292   2 x 10 8
200   3,972,999,029,388   4 x 10 12
300   9,253,082,936,723,602   9 x 10 15
400   6,727,090,051,741,041,926   7 x 10 18
500   2,300,165,032,574,323,995,027   2 x 10 21
600   458,004,788,008,144,308,553,622   5 x 10 23
700   60,378,285,202,834,474,611,028,659   6 x 10 25
800   5,733,052,172,321,422,504,456,911,979   6 x 10 27
900   415,873,681,190,459,054,784,114,365,430   4 x 10 29
1000   24,061,467,864,032,622,473,692,149,727,991   2 x 10 31

Just looking at the exponents on the right, it seems that doubling the number n results in an exponent about 1/2 again as much. So P(2000) should be on the order of 10 31 + (31 / 2) = 10 46.

Euler worked on partition functions, and so did Ramanujan in the 20th century. Something is known about these interesting functions, but I haven't found a simple analytic function that returns a number with these partition functions. Such a formula would be useful for many recreational math problems! Ramanujan found that the natural log of P(n) is asympotic to pi sqrt(2n/3), which gives this approximate formula: 

           e^(pi sqrt(2n/3))
    P(n) = -------------------
               4n sqrt(3)
Figuring this for n = 2000 with my calculator gives P(n) = 4.8 x 1045, close to the estimate. P(2000,10) and Q(2000,10) will of course be much smaller, but they're still very large. I stand by my original answer: lots!

Here are some Web links for further research:

Back to Stumper

Last modified .

Copyright © 2000 by Marc Kummel / mkummel@rain.org