Math puzzles -- the answers
1. [The summation problem]
Consider the integersb_{1} = a_{1} b_{2} = a_{1} + a_{2} b_{3} = a_{1} + a_{2} + a_{3} ... b_{n} = a_{1} + ... + a_{n}Let r_{i} be the remainder of division of b_{i} by n (0 <= r_{i} < n). If all r_{i} are distinct, one of them must be 0. Otherwise, for some 1 <= i < j <= n, r_{i} = r_{j}, so that n divides b_{j} - b_{i} = a_{i+1} + ... + a_{j}.
2. [The Fibonacci number problem]
Let us define f_{i} to be the remainder of division of F_{i} by n (0 <= f_{i} <= n-1). We then have(2.1a) f_{i} = (f_{i-1} + f_{i-2}) mod n for all integers i > 2, and (2.1b) f_{i} = (f_{i+2} - f_{i+1}) mod n for all integers i >= 1Now consider the n^{2}+1 ordered pairs (f_{1},f_{2}), (f_{2},f_{3}), ..., (f_{n2+1},f_{n2+2}). Since there are only n^{2} distinct ordered pairs in {0,1,...,n-1}^{2}, we must have 0 < i < j <= n^{2}+1 with
(f_{i},f_{i+1}) = (f_{j},f_{j+1})A simple inductive reasoning using Eqns (2.1) guarantees that
(2.2) f_{i+k} = f_{j+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
f_{d+1} = f_{1} = 1 f_{d+2} = f_{2} = 1But then Eqn (2.1b) implies
f_{d} = (f_{d+2} - f_{d+1}) mod n = 0
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 = p_{1}^{e1} p_{2}^{e2} ... p_{r}^{er} be the prime factorization of i, where p_{1}, p_{2}, ..., p_{r} are distinct primes and e_{1}, e_{2}, ..., e_{r} are positive integers. Then the number of factors of i is (e_{1} + 1) (e_{2} + 1) ... (e_{r} + 1) which is odd if and only if all e_{i}, i = 1, ..., r are even.
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 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_{0} after a_{i} `p-steps' and b_{i} `q-steps' (in some `given' order). [Note that here we use the terminology from random walks.] Then
(4.2) a_{i}+ b_{i} = iWe are looking for an i such that
a_{i+p+q} = a_{i} + q b_{i+p+q} = b_{i} + pso that
x_{i+p+q} = x_{i} + q.p + p(-q) = x_{i}This motivates us to define f(i) for i = 0, 1,..., n-p-q, as
(4.3) f(i) = (a_{i+p+q}- a_{i}- q) - (b_{i+p+q}- b_{i}- p)We also have from (4.2)
(4.4) a_{i+p+q}+ b_{i+p+q} = a_{i}+ b_{i} + (p + q)Combining these gives
(4.5a) f(i) = 2(a_{i+p+q}- a_{i}) - 2q (4.5b) = 2p - 2(b_{i+p+q}- b_{i})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))a_{p+q}- a_{0} > q a_{2(p+q)}- a_{p+q} > q ... a_{k(p+q)}- a_{(k-1)(p+q)} > q
Summing up and using (4.1) and the fact that a_{0}=0 givea_{n} > kq
It's easy to check that a_{n} = 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.
5. [The partition problem]
Let us arrange the numbers 1, 2, ..., n^{2} 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(n^{2} + 1)/2as desired.
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}.
Solution by: Abhijit Das (Barda)
- 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
- Partition {1, 2, ..., 2n} as U_{i}^{n}_{= 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
A_{1} = {1, 2, 4, 8, 16} A_{2} = {3, 6, 12} A_{3} = {5, 10} A_{4} = {7, 14} A_{5} = {9} A_{6} = {11} A_{7} = {13} A_{8} = {15}
Solution by: Alexander Bogomolny - 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} B_{1} = {9, 10} B_{2} = {15, 16} C_{1} = {4} C_{2} = {6} C_{3} = {8} C_{4} = {12} C_{5} = {14} C_{6} = {18} C_{7} = {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)
7. [All composite problem]
If n is even, then 2 divides n^{4} + 4^{n} and the quotient is clearly greater than 1. So we only consider the case that n is odd. In this case, we writen^{4} + 4^{n} = (n^{2})^{2} + (2^{n})^{2} = (n^{2} + 2^{n})^{2} - 2^{n+1}n^{2}Since n is odd, 2^{n+1}n^{2} is a whole square and therefore we have the factorization
n^{4} + 4^{n} = (n^{2} + 2^{n} + 2^{(n+1)/2} n) (n^{2} + 2^{n} - 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
n^{2} + 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 n^{2} and 2^{(n+1)/2} (2^{(n-1)/2} - n) are greater than 1 and hence we have a nontrivial factorization of n^{4} + 4^{n} for all odd n > 1.
8. [The problem with 132 idli's]
Denote by a_{i} 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 = a_{i} + a_{i+1} + ... + a_{j-1} <= 21 (2) Number of idlis consumed in days i through j = a_{i} + a_{i+1} + ... + a_{j} >= 23where a_{i} + ... + a_{i-1} = 0 and a_{i} + ... + a_{i} = a_{i}. 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 (m_{1} through m_{k}). Then we can write
f(1) = ... = f(n_{1}) = m_{1} < f(n_{1} + 1) = ... = f(n_{1} + n_{2}) = m_{2} < ... < f(n_{1} + ... + n_{k-1} + 1) = ... = f(n_{1} + ... + n_{k-1} + n_{k}) = m_{k}where each n_{i} is greater than 0 and n_{1} + ... + n_{k} = 56. (2) for i = n_{1} gives
(3) a_{n1} + ... + a_{m1} >= 23Similarly (1) for n = 1 gives
(4) a_{1} + ... + a_{m1-1} <= 21Combining (3) and (4) and considering the fact that each a_{i} is positive, we have
a_{m1} >= (23 - 21) + (a_{1} + ... + a_{n1-1}) >= 2 + n_{1}-1 = n_{1} + 1In a similar fashion, we can prove that for each i=1,...,k, we have
a_{mi} >= n_{i} + 1Summing these up gives
Total number of idlis taken in the days m_{i}, i=1,...,k = a_{m1} + ... + a_{mk} >= n_{1} + ... + n_{k} + k = 56 + kDuring 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.
9. [Four squares in AP]
We show that there does not exist a solution in positive integers for A, B, C, D and K satisfyingB^{2} | = | A^{2} + K | } (1) |
C^{2} | = | A^{2} + 2K | |
D^{2} | = | A^{2} + 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) m^{4} - m^{2}l^{2} + l^{4} = k^{2}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
d_{1} | = | B-A | } (3) |
d_{2} | = | C-B | |
d_{3} | = | 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 < mNow we have l(d_{1} + d_{2}) = (C+A)(C-A) = C^{2} - A^{2} = 2K. In a similar fashion, we can derive the last two of the following equations.
l(d_{1}+d_{2}) | = | 2K | } (5) |
m(d_{2}+d_{3}) | = | 2K | |
n(d_{1}+d_{2}+d_{3}) | = | 3K |
From the definitions (3), we also have
d_{1} | = | m - n | } (6) |
d_{3} | = | n - l |
If we now eliminate d_{1}, d_{3}, n and K from equations (5) and (6) and express d_{2} in terms of l and m, we get the following quadratic equation in d_{2}.
(7) 2(m-l)d_{2}^{2} + 2((m-l)^{2} + ml)d_{2} - ml(m-l) = 0The system (1) is solvable if and only if equation (7) has a rational solution for d_{2} for some values of l and m. Now d_{2} has a rational solution if and only if the discriminant of (7) is a whole square, that is, if and only if
(m^{2} - l^{2})^{2} + m^{2}l^{2} = m^{4} - m^{2}l^{2} + l^{4}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 != mNow 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, m^{4} - m^{2}l^{2} + l^{4} = k^{2} 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) (X^{2} - Y^{2})^{2} + X^{2}Y^{2} = X^{4} - X^{2}Y^{2} + Y^{4} = Z^{2}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), g^{4} divides Z^{2} so that X/g, Y/g, Z/g^{2} satisfy (2) and hence Z/g^{2} is in T. By minimality of Z, we must have g = gcd(X,Y) = 1. This implies that gcd(X^{2} - Y^{2}, 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 X^{2} - Y^{2}, XY, Z is a Pythagorean triple with gcd(X^{2} - Y^{2}, XY) = 1. Hence by a characterization of primitive Pythagorean triples, we haveX^{2} - Y^{2} | = | 2xy | } (11) |
XY | = | x^{2} - y^{2} | |
Z | = | x^{2} + y^{2} |
for some integers x > y > 0, gcd(x,y) = 1. Now we have
(X^{2} + Y^{2})^{2} = (X^{2} - Y^{2})^{2} + 4X^{2}Y^{2} = 4((x^{2} - y^{2})^{2} + x^{2}y^{2})Therefore, x,y,(X^{2} + Y^{2})/2 satisfy (2) and hence (X^{2} + Y^{2})/2 is in T. By (10), X^{2}Y^{2} < Z^{2}, so that
(X^{2} + Y^{2})^{2} = (X^{2} - Y^{2})^{2} + X^{2}Y^{2} + 3X^{2}Y^{2} = Z^{2} + 3X^{2}Y^{2} < 4Z^{2}This implies that (X^{2} + Y^{2})/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 writeX^{2} - Y^{2} | = | x^{2} - y^{2} | } (12) |
XY | = | 2xy | |
Z | = | x^{2} + y^{2} |
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 | = | 2^{e}p_{1}^{a1} ... p_{s}^{as} q_{1}^{b1} ... q_{t}^{bt} | } (13) |
Y | = | p_{s+1}^{as+1} ... p_{s+u}^{as+u} q_{t+1}^{bt+1} ... q_{t+v}^{bt+v} | |
x | = | 2^{e-1}p_{1}^{a1} ... p_{s+u}^{as+u} | |
y | = | q_{1}^{b1} ... q_{t+v}^{bt+v} |
where the odd primes p_{i} and q_{j} are all distinct. We further define the following GCDs.
P_{1} | = | gcd(X,x) | = | 2^{e-1}p_{1}^{a1} ... p_{s}^{as} | } (14) |
P_{2} | = | gcd(X,y) | = | q_{1}^{b1} ... q_{t}^{bt} | |
Q_{1} | = | gcd(Y,x) | = | p_{s+1}^{as+1} ... p_{s+u}^{as+u} | |
Q_{2} | = | gcd(Y,y) | = | q_{t+1}^{bt+1} ... q_{t+v}^{bt+v} |
We then have
(15) X = 2P_{1}P_{2}, Y = Q_{1}Q_{2}, x = P_{1}Q_{1}, y = P_{2}Q_{2}Plugging in these values in the first equation of (12) gives
(16) P_{1}^{2} (4P_{2}^{2} - Q_{1}^{2}) = Q_{2}^{2} (Q_{1}^{2} - P_{2}^{2})Now by (14) gcd(P_{1},Q_{2}) = 1. Therefore there is an integer r such that
Q_{1}^{2} - P_{2}^{2} | = | r P_{1}^{2} | } (17) |
4P_{2}^{2} - Q_{1}^{2} | = | r Q_{2}^{2} |
From these equations we get
3P_{2}^{2} = | r (P_{1}^{2} + Q_{2}^{2}) | } (18) |
3Q_{1}^{2} = | r (4P_{1}^{2} + Q_{2}^{2}) |
We thus have 3 = gcd(3P_{2}^{2}, 3Q_{1}^{2}) = r.gcd(P_{1}^{2}+Q_{2}^{2}, 4P_{1}^{2}+Q_{2}^{2}) = r.gcd(P_{1}^{2}+Q_{2}^{2}, 3P_{1}^{2}). Now P_{1} and Q_{2} cannot be both divisible by 3 (since they are coprime). Hence considering all possible values of P_{1} and Q_{2} mod 3, we see that P_{1}^{2}+Q_{2}^{2} is congruent to 1 or 2 mod 3. This forces r = 3 and we have from Eqns (18)
P_{2}^{2} | = | P_{1}^{2}+Q_{2}^{2} | } (19) |
Q_{1}^{2} | = | 4P_{1}^{2}+Q_{2}^{2} |
2P_{1}, Q_{2}, Q_{1} is, therefore, a primitive Pythagorean triple and we have integers c > d > 0, gcd(c,d) = 1 such that
2P_{1} = 2cd, Q_{2} = c^{2} - d^{2}, Q_{1} = c^{2} + d^{2}But then the first equation of (19) implies that (c^{2} - d^{2})^{2} + c^{2}d^{2} = P_{2}^{2}. Hence c,d,P_{2} is a solution of (2) and P_{2} is in T. But Z = x^{2} + y^{2} > y^{2} = P_{2}^{2}Q_{2}^{2} >= P_{2}. This once again contradicts the minimality of Z in T.
An auxiliary result
Let a, b and c be integers such that a^{2} + b^{2} = c^{2}. 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 a^{2} + b^{2} = c^{2} with b even are a = r^{2} - s^{2}, b = 2rs and z = r^{2} + s^{2}, 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.
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