Math puzzles -- the questions
1. [The summation problem]
Given n integers a_{1}, a_{2},..., a_{n} (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 {i_{1},...,i_{k}} of indices such that n divides a_{i1} + ... + a_{ik}.2. [The Fibonacci number problem]
Given an integer n > 1, show that there exists a Fibonacci number divisible by n.[Fibonacci numbers F_{i} are defined for integers i >= 1 as
F_{1} = 1 F_{2} = 1 F_{i} = F_{i-1} + F_{i-2} for all i >= 3The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... ]
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 L_{1}, L_{2}, ..., L_{n}; L_{1} = L_{2} = ... = L_{n} = OFF; for (i=1; i<=n; i++) for (j=1; j<=n; j++) if (i divides j) toggle(L_{j});Which of the lamps will be ON after the execution of the above process?
4. [The random walk problem]
Let n, p, q be positive integers with n > p + q. Let x_{0}, x_{1}, ..., x_{n} be integers satisfying the following conditions:(a) x_{0} = x_{n} = 0 (b) for each integer i with 1 <= i <= n, either x_{i} - x_{i-1} = p or x_{i} - x_{i-1} = -qShow that there exists a pair (i,j) of indices with i < j and (i,j) not equal to (0,n) such that x_{i} = x_{j}.
[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.]
5. [The partition problem]
Partition the set of numbers {1,2,...,n^{2}} into n pairwise disjoint subsets each containing n numbers such that the sum of the numbers in each subset is the same (namely, n(n^{2}+1)/2).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- There exist distinct x and y in S such that x - y = 1.
- There exist distinct x and y in S such that x - y = n.
- There exist distinct x and y in S such that x is a multiple of y.
- 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. ]
7. [All composite problem]
Show that the numbers n^{4} + 4^{n} are not prime for all integers n > 1.8. [The problem with 132 idli's]
Suppose you want to eat 132 idlis in a total of 77 successive days such that:- You can eat only an integral number of idlis per day.
- You must eat at least one idli each day.
[ 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, 1997or at the website http://www.seanet.com/~ksbrown/kmath389.htm. The proof, however, cannot be straightaway applied to the case of 22 idlis. ]
9. [Four squares in AP]
There does not exist a solution in positive integers for A, B, C, D and K satisfyingB^{2} | = | A^{2} + K |
C^{2} | = | A^{2} + 2K |
D^{2} | = | A^{2} + 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. ]
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