MATHEMATICS  PROBLEM  130

 

     The odd-even 3x3 determinant game is played by two persons who alternately enter integers in a 3x3 matrix.  Player 1 enters any integer he desires in the empty 3x3 matrix, then Player 2 any integer he desires in a vacant position, and play continues in this way until the matrix is completed with nine integer entries.  Player 1 wins if the resulting determinant is odd and Player 2 wins if the determinant is even.  If both players use optimal strategies, who will win and how?

 

 

 

 

 

 

 

 

 

 

Each midshipman submitting a correct solution with a correct explanation to Problem 130 by 1700 Monday 31 March 2003 will win a cookie.  Submit solutions to Prof. Wardlaw at mathprob@usna.edu (please no attachments!) or via his mailbox in Chauvenet 301.

         

No one submitted a correct solution to Mathematics Problem 129. The problem is a classical combinatorics question and many solutions appear in the literature.  My solution is on the back and on the board.

 

 

 

MATHEMATICS  PROBLEM  129

a.        How many sequences of ten positive integers have a sum less than or equal to a thousand?

b.       How many sequences of ten nonnegative integers have a sum less than or equal to a thousand?

Solution.  a.  Consider the general problem:  How many sequences   of    positive integers have sum  < ?  Method 1:  Recall that  C(a,b)  is the number of subsets of  size  b  chosen from a set of size  a, or the number of combinations of  a  things taken  b  at a time.   Since there are  C(t-1,k-1)  sequences that sum to  t,  there are  C(0-1,k-1) + C(0,k-1) + … +C(k-1,k-1) +C(k,k-1) + C(k+1,k-1) + … + C(s-2,k-1) + C(s-1,k-1)  =  C(k-1,k-1) +C(k,k-1) + C(k+1,k-1) + … + C(s-2,k-1) + C(s-1,k-1)  =  C(k,k) +C(k,k-1) + C(k+1,k-1) + … + C(s-2,k-1) + C(s-1,k-1)  = C(k+1,k) + C(k+1,k-1) + … + C(s-2,k-1) + C(s-1,k-1)  = C(t-1,k) + C(t-1,k-1) +  C(t,k-1) + …+ C(s-2,k-1) + C(s-1,k-1)  = C(t,k) + C(t,k-1) + … + C(s-2,k-1) + C(s-1,k-1)  = C(s-1,k)  + C(s-1,k-1) = C(s,k) = (s!)/((k!)(s-k)!)  sequences that sum to  < s.  (The sum was calculated by noting first that  C(t-1,k-1) = 0  when  t < k, then that  C(k-1,k-1) = 1 = C(k,k), and finally repeatedly adding the leftmost two terms using the identity  C(u,k) + C(u,k-1) = C(u+1,k).)  Hence,   C(s,k) =  (s!)/((k!)(s-k)!)  sequences   of    positive integers have sum  < .   Method 2.  The  C(s,k)  subsets of size  k  of the set  {1, 2, 3, … , s}  are in  1-1  correspondence with the increasing sequences  (s₁,s₂,…,s_k)  with  1 < s₁ < s₂ < … < s_k < s,  and the latter sequences are in  1-1 correspondence with the sequences   of    positive integers which have sum  < .  (These are obtained by taking   a₁ = s₁  and  a_j = s_j – s_j-1  for  j = 2, 3, … , k. )  So , there are  C(s,k) =  (s!)/((k!)(s-k)!)  sequences   of    positive integers have sum  < .   In particular, there are

C(1000,10) = (1000!)/((10!)(990!)) =

1000x999x998x997x996x995x994x993x992x991/(10x9x8x7x6x5x4x3x2x1)

=  

sequences of  10  positive integers which have sum  less than or equal to 1000.

                b.  Consider the general problem:  How many sequences   of    nonnegative integers have sum   < ?   We can convert this problem to the positive integer problem in part  a  by taking   and replacing    by  .  Hence there are  C(s+k,k) = (s+k)!/((s!)(k!)) sequences of  k  nonnegative integers which have sum  <  s.  In particular, there are 

C(1010,10) = 1010x1009x1008x…x1001/(10x9x8x…x1) =

sequences of ten nonnegative integers which have sum less than or equal to 1000.