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.
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
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.
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).
- f(i) is always even (by Eqns (4.5)).
- When both f(i) and f(i+1) are defined,
f(i+1)-f(i) is 0, 2 or -2. (easy check)
- 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.
- f(i) >= 0 for some i in {0,1,...,n-p-q}.
The proof is similar.
- 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.
Go back
5. [The partition problem]
Let us arrange the numbers 1, 2, ..., n2 as in the following array.
| 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
as desired.
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.
- Partition {1, 2, ..., 2n} as {1, 2} U {3, 4} U ... U {2n-1, 2n}.
- 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.
- 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}
- 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?
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.
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.
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.
Go back
Page maintained by
Abhijit Das (Barda)
Department of Computer Science and Automation
Indian Institute of Science
Bangalore 560 012
INDIA
e-mail: [email protected]
URL: http://in.geocities.com/ad_rab/
Last updated on Nov 12 1998