Math puzzles -- the questions

1. [The summation problem]

Given n integers a1, a2,..., an (not necessarily distinct and not necessarily positive), show that there exists k, 1 <= k <= n, such that the sum of some k of the given integers is divisible by n, that is, there is a subset {i1,...,ik} of indices such that n divides ai1 + ... + aik.

Source: Indranath Sengupta

Hint
The solution

2. [The Fibonacci number problem]

Given an integer n > 1, show that there exists a Fibonacci number divisible by n.

[Fibonacci numbers Fi are defined for integers i >= 1 as 

   F1 = 1
   F2 = 1
   Fi = Fi-1 + Fi-2  for all i >= 3
The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... ]

Source: Indranath Sengupta

Hint
The solution

3. [The n lamps problem]

Suppose we have n lamps numbered 1 through n. Initially all lamps are off. We then carry out the n-step process: in the ith step, we toggle the state of only those lamps whose numbers are multiples of i. (Here toggling the state of a lamp means if the lamp is on, turn it off, and if the lamp is off, turn it on.) In other words, we carry out the following algorithm: 
   lamp L1, L2, ..., Ln;

   L1 = L2 = ... = Ln = OFF;

   for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
         if (i divides j) toggle(Lj);
Which of the lamps will be ON after the execution of the above process?

Source: Pratip Kar

Hint
The solution

4. [The random walk problem]

Let n, p, q be positive integers with n > p + q. Let x0, x1, ..., xn be integers satisfying the following conditions: 
(a) x0 = xn = 0
(b) for each integer i with 1 <= i <= n,
         either  xi - xi-1 = p
             or  xi - xi-1 = -q
Show that there exists a pair (i,j) of indices with i < j and (i,j) not equal to (0,n) such that xi = xj.

[This is similar to the random walk problem. That is, at every step you can make one of two moves: either p units in the +ve direction or q units in the -ve direction. The difference is that there is no probability associated with each move here.]

Source: International Math Olympiad 1996

Hint
The solution

5. [The partition problem]

Partition the set of numbers {1,2,...,n2} into n pairwise disjoint subsets each containing n numbers such that the sum of the numbers in each subset is the same (namely, n(n2+1)/2).

Source: Mindsport, The Times of India

Hint
The solution

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

Let S be an arbitrary subset of the set {1, 2, ..., 2n}. If S contains n+1 elements, then show that
  1. There exist distinct x and y in S such that x - y = 1.
  2. There exist distinct x and y in S such that x - y = n.
  3. There exist distinct x and y in S such that x is a multiple of y.
  4. There exist distinct x and y in S such that x is relatively prime to y.

[ Solutions of these problems are nice applications of the pigeon-hole principle which states that

If n pigeons are put into m pigeonholes where n > m, then there is a hole with more than one pigeon.
There are several generalizations of this statement. Though the statement of the pigeon-hole principle is absolutely obvious and hardly calls for any proof (Well! If you are interested in a formal proof, go ahead. It's extremely easy.), it has numerous interesting applications. In addition to the ones listed in this problem, we have used this principle for solving the summation problem. You may look at this website for a detailed discussion on this principle and for many applications of it. ]

Source: Various text books on combinatorics

Hint
The solution

7. [All composite problem]

Show that the numbers n4 + 4n are not prime for all integers n > 1.

Source: An M.E. student from the department of CSA

Hint
The solution

8. [The problem with 132 idli's]

Suppose you want to eat 132 idlis in a total of 77 successive days such that:
  1. You can eat only an integral number of idlis per day.
  2. You must eat at least one idli each day.
Show that whatever be the way you eat the idlis, there will be a set of successive days during which you must consume a total number of exactly 22 idlis.

[ Idli is a white fluffy food prepared from rice. Rice grains are first ground and water is added to it. The pulp is then steamed in a special device to produce idlis. This food is very popular in the southern part of India. In case you do not like to eat idlis for some reason or other, eat whatever you like: cakes or biscuits or fish fries or whatever. Don't change the numbers in the problem ...

When 22 in the statement of this problem is replaced by 21, a very elegant solution for the problem exists that uses the pigeon-hole principle. The solution can be found in Example 4.4, p 128 of

C. L. Liu, `Elements of Discrete Mathematics', 2nd Edition, McGraw Hill, 1997
or at the website http://www.seanet.com/~ksbrown/kmath389.htm. The proof, however, cannot be straightaway applied to the case of 22 idlis. ]

Source: Nirmal Kumar Sancheti, Motorola, India

Hint
The solution

9. [Four squares in AP]

There does not exist a solution in positive integers for A, B, C, D and K satisfying

B2=A2 + K
C2=A2 + 2K
D2=A2 + 3K

[ L.E. Dickson in 1952 proved that four distinct whole squares can not be in arithmetic progression (AP). The proof can be found in pages 435-440 of

Dickson, L. E., History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Chelsea, 1952.
Kevin S Brown claimed that he and many other people didn't understand the proof. In particular, Dickson has assumed a particular form of six expressions. It's apparently not clear why all these would hold simultaneously. Brown could not give a justification. So he devised a proof himself. Brown's homepage links to a lot of other problems in number theory and in other branches of mathematics.

The proof presented here is a little more involved than Brown's. Both this proof and Brown's proof reach contradiction by Fermat's method of infinite descent.

Note that this is not a very easy problem to solve. In my opinion, this is the most difficult one in this page. Please let me know, if you find a simpler solution. ]

Source: John Stewart, Florida

Hint
The solution

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