Math puzzles -- the hints
1. [The summation problem]
Consider the integers b_{i} = a_{1} + ... + a_{i} for i = 1,...,n.2. [The Fibonacci number problem]
Define f_{i} to be the remainder of division of F_{i} by n. Try to prove that the sequence f_{1}, f_{2}, f_{3}, ... is periodic of period d, say. Then f_{d} = 0.3. [The n lamps problem]
The lamp numbered i will be ON if and only if i has an odd number of factors and i has an odd number of factors if and only if i is a whole square.4. [The random walk problem]
Assume p and q are relatively prime. Show that there exists i, 0 <= i <= n-p-q, such that x_{i} = x_{i+p+q}. More specifically, show that there exists i such that x_{i+p+q} is reached from x_{i} by p `q-steps' and q `p-steps' (in some order).5. [The partition problem]
Consider the 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 |
6. [The (n+1)-subset 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}.
- Partition {1, 2, ..., 2n} as U_{i}^{n}_{= 1} A_{i} where A_{i} consists of numbers of form 2^{k}(2i-1) for all possible non-negative integers k for which 2^{k}(2i-1) is less than or equal to 2n.
- Partition {1, 2, ..., 2n} as a disjoint union of n subsets as follows: One subset consists of 1 and all primes less than (or equal to, in the pathological case n=1) 2n. For every composite odd number m less than 2n, form a subset {m, m+1}. For every composite even number m (less than 2n) for which m - 1 is prime, the singleton {m} is a constituent of the partition.
7. [All composite problem]
For odd n, express n^{4} + 4^{n} as a difference of two squares.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, define for each i=1,...,56, the function f(i) = j such thatNumber of idlis consumed in days i through j-1 = a_{i} + ... + a_{j-1} <= 21 Number of idlis consumed in days i through j = a_{i} + ... + a_{j} >= 23Now show that if f(1),f(2),...,f(56) assume k different values, then you must consume at least 56 + k idlis in these k days. During the remaining 77 - k days you must consume at least 77 - k idlis. This requires a total of at least 133 idlis, a contradiction.
9. [Four squares in AP]
Show that the given system has a solution in positive integers for A, B, C, D and K if and only if the Diophantine equationm^{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. 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.
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