Math puzzles -- the answers

1. [The summation problem]

   b1 = a1
   b2 = a1 + a2
   b3 = a1 + a2 + a3
     ...
   bn = a1 + ... + an

Go back

2. [The Fibonacci number problem]

(2.1a)   fi = (fi-1 + fi-2) mod n  for all integers i > 2, and
(2.1b)   fi = (fi+2 - fi+1) mod n  for all integers i >= 1

   (fi,fi+1) = (fj,fj+1)

(2.2)  fi+k = fj+k   for all integers k >= -(i-1)

   fd+1 = f1 = 1
   fd+2 = f2 = 1

   fd = (fd+2 - fd+1) mod n = 0

Go back

3. [The n lamps problem]

A lamp will be ON if and only if its state is toggled an odd number of times. A lamp is toggled once for each (positive) factor of its number. That is, the lamp numbered i will be ON if and only if i has an odd number of factors. Let i = p₁^e₁ p₂^e₂ ... p_r^e_r be the prime factorization of i, where p₁, p₂, ..., p_r are distinct primes and e₁, e₂, ..., e_r are positive integers. Then the number of factors of i is (e₁ + 1) (e₂ + 1) ... (e_r + 1) which is odd if and only if all e_i, i = 1, ..., r are even.

Go back

4. [The random walk problem]

(4.1)  n = k(p + q)  for some integer k > 1

We want to show that there exists i, 0 <= i <= n-p-q, such that x_i = x_i+p+q. To this end, we define an integer-valued function f(i) for each i = 0, 1,..., n-p-q. Before that we introduce a few notations. Let x_i be reached from x₀ after a_i `p-steps' and b<sub>i</sub> `q-steps' (in some `given' order). [Note that here we use the terminology from random walks.] Then

(4.2)  ai+ bi = i

   ai+p+q = ai + q
   bi+p+q = bi + p

   xi+p+q = xi + q.p + p(-q) = xi

(4.3)  f(i) = (ai+p+q- ai- q) - (bi+p+q- bi- p)

(4.4)  ai+p+q+ bi+p+q = ai+ bi + (p + q)

(4.5a)  f(i) = 2(ai+p+q- ai) - 2q
(4.5b)       = 2p - 2(bi+p+q- bi)

1. f(i) is always even (by Eqns (4.5)).
2. When both f(i) and f(i+1) are defined, f(i+1)-f(i) is 0, 2 or -2. (easy check)
3. f(i) <= 0 for some i in {0,1,...,n-p-q}.
   This assertion needs a non-trivial check. Assume otherwise, that is, f(i) > 0 for all i in {0,1,...,n-p-q}. We then use (4.5a) for f(0), f(p+q), f(2(p+q)), ..., f((k-1)(p+q))

      ap+q- a0 > q
      a2(p+q)- ap+q > q
         ...
      ak(p+q)- a(k-1)(p+q) > q
   

   Summing up and using (4.1) and the fact that a₀=0 give

      an > kq
   

   It's easy to check that a_n = kq. This leads to a contradiction.
4. f(i) >= 0 for some i in {0,1,...,n-p-q}.
   The proof is similar.
5. f(i) = 0 for some i in {0,1,...,n-p-q}.
   By properties 4 and 5 there exist s, t in {0,1,...,n-p-q} such that f(s) <= 0 and f(t) >= 0. If f(s) = 0 or f(t) = 0, we are done. So assume f(s) < 0 and f(t) > 0. Assume s < t. Then properties 1 and 2 imply that there exists i with s < i < t, such that f(i)=0.

Go back

5. [The partition problem]

1	2	3	...	n
2n	n+1	n+2	...	2n-1
3n-1	3n	2n+1	...	3n-2
...	...	...	...	...
(n-1)n + 2	(n-1)n + 3	(n-1)n + 4	...	(n-1)n + 1

Our claim is that the columns of the above array constitute the desired partition. To prove that our claim is justified, we write another array that is derived from the previous one in the following way. Subtract 0 from each element in the first row, subtract n from each element in the second row, subtract 2n from each element in the third row, ..., subtract (n-1)n from each element in the last (nth) row. This gives

1	2	3	...	n
n	1	2	...	n-1
n-1	n	1	...	n-2
...	...	...	...	...
2	3	4	...	1

Note that each column in the derived array is a permutation of the numbers 1, 2, ..., n. Hence the sum of the elements in each column of the original array is

   (1 + 2 + 3 + ... + n) + (0 + n + 2n + ... + (n-1)n)
      = n(n + 1)/2  + n . n(n - 1)/2
      = n(n2 + 1)/2

Go back

6. [The (n+1)-subset problem]

1. Partition {1, 2, ..., 2n} as {1, 2} U {3, 4} U ... U {2n-1, 2n}.
   Solution by: Abhijit Das (Barda)

2. Partition {1, 2, ..., 2n} as {1, n+1} U {2, n+2} U ... U {n, 2n}. In this case, if S contains both the members of, say, {i, n+i}, the problem is solved since (n + i) - i = n.
   Solution by: Alexander Bogomolny

3. Partition {1, 2, ..., 2n} as U_iⁿ_{= 1} A_i where A_i consists of numbers of form 2^t(2i-1) for all possible non-negative integers t for which 2^t(2i-1) is less than or equal to 2n. If two integers belong to a particular A_i, then their prime factorizations differ only in the power of 2 and hence the integer with the smaller exponent of 2 divides the other.

   As an example we take the case n=8. The partition is

      A1  = {1, 2, 4, 8, 16}
      A2  = {3, 6, 12}
      A3  = {5, 10}
      A4  = {7, 14}
      A5  = {9}
      A6  = {11}
      A7  = {13}
      A8  = {15}
   

   Solution by: Alexander Bogomolny

4. For this problem, we write N = {1, 2, ..., 2n} = A U (U B_i) U (U C_j). Here A = {1} U {p | p is a prime, 2 <= p <= 2n}. Let the cardinality of A be k. Then there exist (n-k+1) composite odd integers in N. For each such composite integer m, we construct a B_i as B_i = {m,m+1}. This leaves us with 2n - k - 2(n-k+1) = k-2 even composite numbers of N that are included neither in A nor in any of the B_i. For each such number m, we construct a C_j = {m}. Thus the partition contains a total of 1 + (n-k+1) + (k-2) = n subsets. Each subset of the partition has the property that if two distinct integers belong to that subset, then those two integers are coprime.

   As an example, we have the following partition for n=10.

      A = {1, 2, 3, 5, 7, 11, 13, 17, 19}
      B1 = {9, 10}
      B2 = {15, 16}
      C1 = {4}
      C2 = {6}
      C3 = {8}
      C4 = {12}
      C5 = {14}
      C6 = {18}
      C7 = {20}
   

   Note: The partition of 1 also works and that's much simpler. But don't you feel (like me) that the one presented here is much more elegant?

   Solution by: Abhijit Das (Barda)

Go back

7. [All composite problem]

n4 + 4n = (n2)2 + (2n)2 = (n2 + 2n)2 - 2n+1n2

n4 + 4n = (n2 + 2n + 2(n+1)/2 n) (n2 + 2n - 2(n+1)/2 n)

n2 + 2(n+1)/2 (2(n-1)/2 - n)

Go back

8. [The problem with 132 idli's]

(1) Number of idlis consumed in days i through j-1 = ai + ai+1 + ... + aj-1 <= 21
(2) Number of idlis consumed in days i through j = ai + ai+1 + ... + aj >= 23

   f(1) = ... = f(n1) = m1
 < f(n1 + 1) = ... = f(n1 + n2) = m2
 < ...
 < f(n1 + ... + nk-1 + 1) = ... = f(n1 + ... + nk-1 + nk) = mk

(3) an1 + ... + am1 >= 23

(4) a1 + ... + am1-1 <= 21

am1 >= (23 - 21) + (a1 + ... + an1-1) >= 2 + n1-1 = n1 + 1

ami >= ni + 1

Total number of idlis taken in the days mi, i=1,...,k
 =  am1 + ... + amk
>=  n1 + ... + nk + k
 =  56 + k

Go back

9. [Four squares in AP]

We reduce the problem to the solvability of a Diophantine equation. More precisely, we show that the system (1) has a solution in positive integers for A, B, C, D and K if and only if the Diophantine equation

(2)   m4 - m2l2 + l4 = k2

First of all we introduce the following variables

Since we are searching for a solution with 0 < A < B < C < D, we must have the following inequality from the definition of l, m and n

(4)   0 < l < n < m

From the definitions (3), we also have

If we now eliminate d₁, d₃, n and K from equations (5) and (6) and express d₂ in terms of l and m, we get the following quadratic equation in d₂.

(7)   2(m-l)d22 + 2((m-l)2 + ml)d2 - ml(m-l) = 0

      (m2 - l2)2 + m2l2 = m4 - m2l2 + l4

(8)   l > 0,  m > 0,  l != m

(9)   T = { k | 0 < k integer,
                m4 - m2l2 + l4 = k2 for some integers l > 0, m > 0, l != m }

(10)   (X2 - Y2)2 + X2Y2 = X4 - X2Y2 + Y4 = Z2

Let g = gcd(X,Y). Then by (10), g⁴ divides Z² so that X/g, Y/g, Z/g² satisfy (2) and hence Z/g² is in T. By minimality of Z, we must have g = gcd(X,Y) = 1. This implies that gcd(X² - Y², XY)=1. Since X and Y are coprime, they cannot be both even. We, therefore, consider the following two cases.

X and Y are both odd

for some integers x > y > 0, gcd(x,y) = 1. Now we have

      (X2 + Y2)2 = (X2 - Y2)2 + 4X2Y2 = 4((x2 - y2)2 + x2y2)

      (X2 + Y2)2 = (X2 - Y2)2 + X2Y2 + 3X2Y2 = Z2 + 3X2Y2 < 4Z2

X and Y have opposite parities

for some integers x > y > 0, gcd(x,y) = 1. x and y have opposite parity. We assume that x is even and y is odd. The other case can be treated similarly. We start with the following prime factorizations of X, Y, x and y, that comply with the equations XY = 2xy and gcd(X,Y) = gcd(x,y) = 1.

where the odd primes p_i and q_j are all distinct. We further define the following GCDs.

We then have

(15)  X = 2P1P2, Y = Q1Q2, x = P1Q1, y = P2Q2

(16)  P12 (4P22 - Q12) = Q22 (Q12 - P22)

From these equations we get

We thus have 3 = gcd(3P₂², 3Q₁²) = r.gcd(P₁²+Q₂², 4P₁²+Q₂²) = r.gcd(P₁²+Q₂², 3P₁²). Now P₁ and Q₂ cannot be both divisible by 3 (since they are coprime). Hence considering all possible values of P₁ and Q₂ mod 3, we see that P₁²+Q₂² is congruent to 1 or 2 mod 3. This forces r = 3 and we have from Eqns (18)

2P₁, Q₂, Q₁ is, therefore, a primitive Pythagorean triple and we have integers c > d > 0, gcd(c,d) = 1 such that

      2P1 = 2cd,  Q2 = c2 - d2,  Q1 = c2 + d2

An auxiliary result

Theorem The positive primitive solutions of a² + b² = c² with b even are a = r² - s², b = 2rs and z = r² + s², where r and s are arbitrary integers of opposite parity with r > s > 0 and gcd(r,s) = 1.

Proof See Theorem (5.1) of

I. Niven and H. S. Zuckerman, `An introduction to the Theory of Numbers', third edition, John Wiley & Sons, Inc.

Go back

Page maintained by

Last updated on Nov 12 1998

This page hosted by    Get your own Free Home Page