Math puzzles -- the answers

Math puzzles -- the answers

1. [The summation problem]

Consider the integers
   b1 = a1
   b2 = a1 + a2
   b3 = a1 + a2 + a3
     ...
   bn = a1 + ... + an
Let ri be the remainder of division of bi by n (0 <= ri < n). If all ri are distinct, one of them must be 0. Otherwise, for some 1 <= i < j <= n, ri = rj, so that n divides bj - bi = ai+1 + ... + aj.

Solution by: Abhijit Das (Barda)

Go back


2. [The Fibonacci number problem]

Let us define fi to be the remainder of division of Fi by n (0 <= fi <= n-1). We then have
(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
Now consider the n2+1 ordered pairs (f1,f2), (f2,f3), ..., (fn2+1,fn2+2). Since there are only n2 distinct ordered pairs in {0,1,...,n-1}2, we must have 0 < i < j <= n2+1 with
   (fi,fi+1) = (fj,fj+1)
A simple inductive reasoning using Eqns (2.1) guarantees that
(2.2)  fi+k = fj+k   for all integers k >= -(i-1)
Let d=j-i. (It is easy to see that d>2.) Putting k = -(i-1) and k = -(i-2) in Eqn(2.2) gives
   fd+1 = f1 = 1
   fd+2 = f2 = 1
But then Eqn (2.1b) implies
   fd = (fd+2 - fd+1) mod n = 0

Solution by: Abhijit Das (Barda)

Go back


3. [The n lamps problem]

The answer is: The lamp numbered i will be ON if and only if i is a whole square. Let us now justify this.

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 = p1e1 p2e2 ... prer be the prime factorization of i, where p1, p2, ..., pr are distinct primes and e1, e2, ..., er are positive integers. Then the number of factors of i is (e1 + 1) (e2 + 1) ... (er + 1) which is odd if and only if all ei, i = 1, ..., r are even.

Solution by: Abhi Dattasharma and Abhijit Das (Barda)

Go back


4. [The random walk problem]

We may assume that p and q are relatively prime, because if not, we replace p and q by p/gcd(p,q) and q/gcd(p,q) respectively and follow similar logic as we will do here. This assumption implies that n is an integral multiple of p+q (easy check), that is,
(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 xi = xi+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 xi be reached from x0 after ai `p-steps' and bi `q-steps' (in some `given' order). [Note that here we use the terminology from random walks.] Then

(4.2)  ai+ bi = i
We are looking for an i such that
   ai+p+q = ai + q
   bi+p+q = bi + p
so that
   xi+p+q = xi + q.p + p(-q) = xi
This motivates us to define f(i) for i = 0, 1,..., n-p-q, as
(4.3)  f(i) = (ai+p+q- ai- q) - (bi+p+q- bi- p)
We also have from (4.2)
(4.4)  ai+p+q+ bi+p+q = ai+ bi + (p + q)
Combining these gives
(4.5a)  f(i) = 2(ai+p+q- ai) - 2q
(4.5b)       = 2p - 2(bi+p+q- bi)
Let us now investigate the properties of f(i).
  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 a0=0 give
       an > kq
    
    It's easy to check that an = 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.
Property 5 of f in conjunction with Eqns (4.5) then shows that we have got the desired i.

Solution by: Abhijit Das (Barda) and Manojit Chattopadhyay

Go back


5. [The partition problem]

Let us arrange the numbers 1, 2, ..., n2 as in the following array.

123...n
2nn+1n+2...2n-1
3n-13n2n+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

123...n
n12...n-1
n-1n1...n-2
...............
234...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
as desired.

Solution by: Abhijit Das (Barda)

Go back


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

For each of the four problems, we first express the set N = {1, 2, ..., 2n} as a union of (exactly) n disjoint subsets. (This is called a partitioning of the set N.) Since S contains n+1 numbers, the pigeon-hole principle guarantees that there will be at least one subset in the partition that contains 2 or more elements of S. The partitioning is done in such a way that existence of a subset in the partition containing 2 elements of S solves our 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 Uin= 1 Ai where Ai consists of numbers of form 2t(2i-1) for all possible non-negative integers t for which 2t(2i-1) is less than or equal to 2n. If two integers belong to a particular Ai, 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 Bi) U (U Cj). 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 Bi as Bi = {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 Bi. For each such number m, we construct a Cj = {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]

If n is even, then 2 divides n4 + 4n and the quotient is clearly greater than 1. So we only consider the case that n is odd. In this case, we write
n4 + 4n = (n2)2 + (2n)2 = (n2 + 2n)2 - 2n+1n2
Since n is odd, 2n+1n2 is a whole square and therefore we have the factorization
n4 + 4n = (n2 + 2n + 2(n+1)/2 n) (n2 + 2n - 2(n+1)/2 n)
The first factor on the right is clearly greater than 1 for all odd integers n > 1. The second factor can be rewritten as
n2 + 2(n+1)/2 (2(n-1)/2 - n)
This factor has the values 5 and 17 for n = 3 and n = 5 respectively. For odd n > 5, both n2 and 2(n+1)/2 (2(n-1)/2 - n) are greater than 1 and hence we have a nontrivial factorization of n4 + 4n for all odd n > 1.

Solution by: Abhijit Das (Barda)

Go back


8. [The problem with 132 idli's]

Denote by ai the number of idlis you eat on the ith day. Now assume that no set of successive days exists during which you consume 22 idlis. If that is the case, we can define for each i=1,...,56, the function f(i) = j such that
(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
where ai + ... + ai-1 = 0 and ai + ... + ai = ai. It's easy to see that f(1),f(2),...,f(56) is a monotonic increasing sequence (not necessarily strict). Assume that f(1),f(2),...,f(56) assume k different values (m1 through mk). Then we can write
   f(1) = ... = f(n1) = m1
 < f(n1 + 1) = ... = f(n1 + n2) = m2
 < ...
 < f(n1 + ... + nk-1 + 1) = ... = f(n1 + ... + nk-1 + nk) = mk
where each ni is greater than 0 and n1 + ... + nk = 56. (2) for i = n1 gives
(3) an1 + ... + am1 >= 23
Similarly (1) for n = 1 gives
(4) a1 + ... + am1-1 <= 21
Combining (3) and (4) and considering the fact that each ai is positive, we have
am1 >= (23 - 21) + (a1 + ... + an1-1) >= 2 + n1-1 = n1 + 1
In a similar fashion, we can prove that for each i=1,...,k, we have
ami >= ni + 1
Summing these up gives
Total number of idlis taken in the days mi, i=1,...,k
 =  am1 + ... + amk
>=  n1 + ... + nk + k
 =  56 + k
During the remaining 77 - k days, you must consume at least 77 - k idlis. This means that total number of idlis consumed in 77 days is >= (56 + k) + (77 - k) = 133, a contradiction.

Solution by: Abhijit Das (Barda)

Go back


9. [Four squares in AP]

We show that there does not exist a solution in positive integers for A, B, C, D and K satisfying

B2 = A2 + K      }  (1)
C2 = A2 + 2K
D2 = A2 + 3K

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
has a solution for integer values of m, l and k subject to the condition l > 0, m > 0, l != m. We assume that this Diophantine equation has a solution and show that for every solution m, l, k, there is another solution m', l', k' with k' < k. Therefore, if we let T denote the set of all natural numbers k such that for some m and l, the three numbers m, l, k satisfy the given Diophantine equation subject to the constraint stated above, then T does not have a smallest element. This proves that T is empty. This method of proving an assertion is called Fermat's method of infinite descent and is based on the well-ordering of the set of natural numbers.

First of all we introduce the following variables

d1 = B-A     }  (3)
d2 = C-B
d3 = D-C
 
l = C+A
m = D+B
n = D+A

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
Now we have l(d1 + d2) = (C+A)(C-A) = C2 - A2 = 2K. In a similar fashion, we can derive the last two of the following equations.

l(d1+d2) = 2K     }  (5)
m(d2+d3) = 2K
n(d1+d2+d3) = 3K

From the definitions (3), we also have

d1 = m - n     }  (6)
d3 = n - l

If we now eliminate d1, d3, n and K from equations (5) and (6) and express d2 in terms of l and m, we get the following quadratic equation in d2.

(7)   2(m-l)d22 + 2((m-l)2 + ml)d2 - ml(m-l) = 0
The system (1) is solvable if and only if equation (7) has a rational solution for d2 for some values of l and m. Now d2 has a rational solution if and only if the discriminant of (7) is a whole square, that is, if and only if
      (m2 - l2)2 + m2l2 = m4 - m2l2 + l4
is a whole square for some values of l and m. Thus we are concerned with the solutions of the Diophantine equation (2). By inequality (4), we are interested in the values of l and m given by
(8)   l > 0,  m > 0,  l != m
Now we show that the Diophantine equation (2) does not have a solution for l, m, k given the inequalities (8). Let us assume otherwise and introduce the set
(9)   T = { k | 0 < k integer,
                m4 - m2l2 + l4 = k2 for some integers l > 0, m > 0, l != m }
By our assumption, T is non-empty and hence has a smallest element, say, Z. Then there exist integers X > 0, Y > 0, X != Y such that
(10)   (X2 - Y2)2 + X2Y2 = X4 - X2Y2 + Y4 = Z2
We will now find an element in T, that is smaller than Z. This contradicts the fact that Z is smallest in T and thereby proves that the assumption that T is non-empty, does not hold.

Let g = gcd(X,Y). Then by (10), g4 divides Z2 so that X/g, Y/g, Z/g2 satisfy (2) and hence Z/g2 is in T. By minimality of Z, we must have g = gcd(X,Y) = 1. This implies that gcd(X2 - Y2, 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

Note that X2 - Y2, XY, Z is a Pythagorean triple with gcd(X2 - Y2, XY) = 1. Hence by a characterization of primitive Pythagorean triples, we have

X2 - Y2 = 2xy     }  (11)
XY = x2 - y2
Z = x2 + y2

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)
Therefore, x,y,(X2 + Y2)/2 satisfy (2) and hence (X2 + Y2)/2 is in T. By (10), X2Y2 < Z2, so that
      (X2 + Y2)2 = (X2 - Y2)2 + X2Y2 + 3X2Y2 = Z2 + 3X2Y2 < 4Z2
This implies that (X2 + Y2)/2 < Z, which contradicts the fact that Z is minimal in T.

X and Y have opposite parities

We consider the case: X is even and Y is odd. The proof for the other case would be similar. Once again we use the characterization of primitive Pythagorean triples to write

X2 - Y2 = x2 - y2     }  (12)
XY = 2xy
Z = x2 + y2

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.

X = 2ep1a1 ... psas q1b1 ... qtbt     }  (13)
Y = ps+1as+1 ... ps+uas+u qt+1bt+1 ... qt+vbt+v
x = 2e-1p1a1 ... ps+uas+u
y = q1b1 ... qt+vbt+v

where the odd primes pi and qj are all distinct. We further define the following GCDs.

P1 = gcd(X,x) = 2e-1p1a1 ... psas     }  (14)
P2 = gcd(X,y) = q1b1 ... qtbt
Q1 = gcd(Y,x) = ps+1as+1 ... ps+uas+u
Q2 = gcd(Y,y) = qt+1bt+1 ... qt+vbt+v

We then have

(15)  X = 2P1P2, Y = Q1Q2, x = P1Q1, y = P2Q2
Plugging in these values in the first equation of (12) gives
(16)  P12 (4P22 - Q12) = Q22 (Q12 - P22)
Now by (14) gcd(P1,Q2) = 1. Therefore there is an integer r such that

Q12 - P22 =r P12     }  (17)
4P22 - Q12 =r Q22

From these equations we get

3P22 =r (P12 + Q22)     }  (18)
3Q12 =r (4P12 + Q22)

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

P22 = P12+Q22     }  (19)
Q12 = 4P12+Q22

2P1, Q2, Q1 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
But then the first equation of (19) implies that (c2 - d2)2 + c2d2 = P22. Hence c,d,P2 is a solution of (2) and P2 is in T. But Z = x2 + y2 > y2 = P22Q22 >= P2. This once again contradicts the minimality of Z in T.


An auxiliary result

Let a, b and c be integers such that a2 + b2 = c2. Then we call a, b, c a Pythagorean triple. If, in addition, gcd(a,b) = 1 and ab != 0, we call the triple a primitive Pythagorean triple.

Theorem The positive primitive solutions of a2 + b2 = c2 with b even are a = r2 - s2, b = 2rs and z = r2 + s2, 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.

Solution by: Abhijit Das (Barda)

Go back


Page maintained by

Abhijit Das (Barda)
Department of Computer Science and Automation
Indian Institute of Science
Bangalore 560 012
INDIA
e-mail: abhij@csa.iisc.ernet.in
URL: http://www.oocities.org/SiliconValley/Lab/6024/

Last updated on Nov 12 1998


This page hosted by    Get your own Free Home Page