Welcome to DF's Problem of the Month Archive

This page was visited times.

Math symbolics in the problems is given in TeX-like format when necessary but notation is almost always self-evident even if you are not a TeXpert.

Difficult parts of the problems are marked with star (*); those parts which do not have an elementary solution (known to me) are marked with double star (**).

=========== July 1997 ==============

There is a camp at the foot of a mountain. Between the camp and the mountain's summit there are 9 rest stops. To have enough energy to get from one stop to the next (or previous) one a climber has to consume one ration pack on his/her way. It is also known that the climber cannot carry more than 3 packs simultaneously. What is the minimum number of ration packs that have to be brought to the camp at the beginning of the trip so that the climber could eventually reach the summit and get back to the camp?

=============== August 1997 ==========

A polynomial p(x) with integer coefficients and a set A of positive integers are such that for any integer x p(x) is divisible by at least one of the integers in A. Prove that one can choose a single number a in A such that p(x) is divisible by a for any integer x.

  • 1. A is finite. (This problem first appeared on St.Petersburg Mathematics Olympiad in 1991).
  • 2. A = { 2^{2^n} + 1 | n =0,1,... }. (*)
  • 3. A = { 2^n + 1 | n =0,1,... }. (**)

    =========== September 1997 ==============

    A convex polytop is given, and each of its faces is assigned a bug circling the contour of the face in the clockwise direction. It is known that every bug moves with some (not necessarily constant) velocity which always exceeds 1cm/hour. Prove that eventually some two bugs will meet on an edge of the polytop. (*)

    ============ October 1997 ==========

    There are n(n+1)/2 coins arranged into a few stacks. Every second one coin from the top of every existing stack is taken and a new stack is created using all these coins. Prove that eventually numbers of coins in the stacks will be 1, 2, 3, ..., n.

    ============ November 1997 ==========

  • (a) There are a few segments that completely cover a bigger one (overlapping is allowed). Prove that if we remove either right or left half of every one of the smaller segments the remaining halves will always cover at least 1/3 of the length of the big segment.

  • (b) What is the greatest possible number k such that if we (in the situation described above) substitute every one of the smaller segments with its subsegment half its length then the "shrunk segments" will cover at least k-th part of the big segment?

  • (c) Item (b) for small squares covering a big square when every one of the small squares is turned into one of its four quarters.

  • (d) Item (c) but now we can shrink small squares into their subsquares with linear dimensions half their initial value.

  • (e) The same questions for a set of arbitrary rectangles covering a big square.

    ============ December 1997 ==========

    Vertices of a finite graph are colored with two colors. Every second each vertex changes its color to the one which prevailed among its neighbors (if neither of two colors prevails then it keeps the old color). Prove that starting at some moment every vertex will either change its color every second or not change color at all. (*)

    ============ January 1998 ==========

    An N x N table is filled with non-negative numbers so that the sum of numbers in any column as well as the sum of numbers in any row equals 1. Prove that it is possible to select N positive numbers no two of which are in the same row or in the same column. (*)

    ============ February 1998 ==========

    Does there exist a function f: N --> N such that f(f(...f(x)..)) = x+1 for any positive integer x (f is applied f(x) times)?

    ====================================

    Also I invite you to try your skills on the current Problem of the Month. Any comments or new solutions are welcome! Write to dfomin@ptc.com or fomin@hotmail.com

    Back to DF-ES Homepage 1