Math puzzles -- the hints

1. [The summation problem]

Consider the integers bi = a1 + ... + ai for i = 1,...,n.

Go back

2. [The Fibonacci number problem]

Define fi to be the remainder of division of Fi by n. Try to prove that the sequence f1, f2, f3, ... is periodic of period d, say. Then fd = 0.

Go back

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.

Go back

4. [The random walk problem]

Assume p and q are relatively prime. Show that there exists i, 0 <= i <= n-p-q, such that xi = xi+p+q. More specifically, show that there exists i such that xi+p+q is reached from xi by p `q-steps' and q `p-steps' (in some order).

Go back

5. [The partition problem]

Consider the 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

Go back

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

  1. Partition {1, 2, ..., 2n} as {1, 2} U {3, 4} U ... U {2n-1, 2n}.

  2. Partition {1, 2, ..., 2n} as {1, n+1} U {2, n+2} U ... U {n, 2n}.

  3. Partition {1, 2, ..., 2n} as Uin= 1 Ai where Ai consists of numbers of form 2k(2i-1) for all possible non-negative integers k for which 2k(2i-1) is less than or equal to 2n.

  4. 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.

Go back

7. [All composite problem]

For odd n, express n4 + 4n as a difference of two squares.

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, define for each i=1,...,56, the function f(i) = j such that 
Number of idlis consumed in days i through j-1 = ai + ... + aj-1 <= 21
Number of idlis consumed in days i through j = ai + ... + aj >= 23
Now 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.

Go back

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 equation 
   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. 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.

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://geocities.datacellar.net/SiliconValley/Lab/6024/

Last updated on Nov 12 1998

This page hosted by    Get your own Free Home Page
1