33rd Eötvös Competition Problems 1929

1.  Coins denomination 1, 2, 10, 20 and 50 are available. How many ways are there of paying 100?

2.  Show that ∑_{i=0 to k} nCi (-x)ⁱ is positive for all 0 ≤ x < 1/n and all k ≤ n, where nCi is the binomial coefficient.

3.  L, M, N are three lines through a point such that the angle between any pair is 60^o. Show that the set of points P in the plane of ABC whose distances from the lines L, M, N are less than a, b, c respectively is the interior of hexagon iff there is a triangle with sides a, b, c. Find the perimeter of this hexagon. 

Solutions

Problem 1

Coins denomination 1, 2, 10, 20 and 50 are available. How many ways are there of paying 100?

Solution

For 2n there are n+1 ways using just the 1 and 2 coins (0, 1, 2, ... or n 2s). Similarly, there are m+1 ways of paying 20m or 20m+10 with just the 10 and 20 coins. Hence using just the 10, 20, 50 coins we get (for example there are 4 ways of paying 70 without using a 50 and 2 ways with, total 6):

0  10  20  30  40  50  60  70  80  90  100
0   1   2   2   3   4   5   6   7   8   10

Hence there are 1·51 + 1·46 + 2·41 + 2·36 + 3·31 + 4·26 + 5·21 + 6·16 + 7·11 + 8·6 + 10·1 = 784 ways in total. 

Problem 2

Show that ∑_{i=0 to k} nCi (-x)ⁱ is positive for all 0 ≤ x < 1/n and all k ≤ n, where nCi is the binomial coefficient.

Solution

The sum is (1 - nx) + (nC1 - nC2 x)x² + (nC3 - nC4 x)x⁴ + ... . There may be an unpaired term at the end, but if so it is non-negative. A typical bracket is nCi(1 - x(n-i)/(i+1) ) > nCi (1 - 1/(i+1) ) > 0. So the sum is positive. 

Problem 3

L, M, N are three lines through a point such that the angle between any pair is 60^o. Show that the set of points P in the plane of ABC whose distances from the lines L, M, N are less than a, b, c respectively is the interior of hexagon iff there is a triangle with sides a, b, c. Find the perimeter of this hexagon.

Solution

P must lie in the strip a distance a either side of L and in the strip a distance b either side of M. So it must lie in the parallelogram PQRS. It must also lie in the strip a distance c either side of N. So we evidently require that AB lies between P and N. Put k = 2/√3. Then QR = 2ka (since the angles are all 60^o). Similarly, PQ = 2kb. Also AQ + QC = 2kc, so PA + CR = 2k(a+b-c). But PA = CR by symmetry and PAB is equilateral, so AB = k(a+b-c). We get a hexagon iff PA = k(a+b-c) > 0 and similar conditions apply if we consider the strip about M relative to the parallelogram given by the strips about L and N, or the strip L about relative to the third parallelogram. Thus we require c < a+b, b < c+a, a < b+c, or a, b, c to form a triangle.

We have also shown that the perimeter of the hexagon is 2k(a+b-c) + 2k(b+c-a) + 2k(c+a-b) = 2k(a+b+c).