Maths Olympiad Prep

Library / /81 of 86

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Estonia

There are sticks of length 11 with a number 11, 22 or 33 written on each of them. There is an unlimited supply of sticks with every number. Two triangles consisting of three sticks are considered different if neither of the triangles can be composed from sticks of the other triangle.

a. How many different triangles consisting of three sticks are possible?

b. From 1818 sticks, one makes an equilateral triangle of side length 33, divided into 99 pairwise different equilateral triangles of side length 11. Find the largest possible sum of the numbers written on the 99 sticks on the boundary of the big triangle.

Figure 1

Solutions — 2

Solution 1

a.
There are 33 triangles having the same number on each side (111111, 222222, 333333). There are 66 triangles having one number on two sides and another number on the third side (112112, 113113, 221221, 223223, 331331, 332332). Only 11 triangle has a different number on every side (123123). Thus there are 1010 different triangles consisting of three sticks in total.

b.
The largest sum of numbers written on 99 sticks is 2727. Suppose that the sum of the numbers on the sticks on the boundary of the big triangle is 2727. This means that all sticks on the boundary have 33 on it. There are 66 different triangles consisting of three sticks having 33 on some side. As the number of small triangles having a side on the boundary of the big triangle is also 66, all 66 different triangles consisting of three sticks and having 33 on some side must occur at the corners or in the middle of a side of the big triangle. As one of these 66 triangles has 33 on every side, but not all sides of a small triangle can lie on the boundary of the big triangle, at least one stick with number 33 lies in the interior of the big triangle. The other small triangle with this stick as a side lies entirely in the interior of the big triangle. This contradicts the previously proved claim that all triangles consisting of three sticks and having 33 on one side lie on the boundary of the big triangle. The contradiction shows that the sum 2727 is impossible.

Figure 24 shows that the sum can be 2626.

Figure 2

Any of Figures 25, 26, 27, 28 and 29 shows that the sum can be 2626.

*Remark:* Figures 24–29 contain all possibilities, modulo rotations and reflections, for obtaining the sum 2626.

Figure 3
Figure 4
Figure 5
Figure 6
Figure 7

Solution 2

a.
The question of the problem is equivalent to the question how many three-digit numbers whose each digit is 11, 22 or 33 and digits are in non-decreasing order do there exist. There are 1010 such numbers (111111, 112112, 113113, 122122, 123123, 133133, 222222, 223223, 233233, 333333).

Figure 2

b.
The largest sum of numbers written on 99 sticks is 2727. Suppose that the sum of the numbers on the sticks on the boundary of the big triangle is 2727. This means that all sticks on the boundary have 33 on it. In all 1010 triangles consisting of three sticks, the number 33 occurs 1010 times in total. To have 99 occurrences on the boundary, the triangle with 33 on every side must definitely be used. As not all sides of a small triangle can lie on the boundary of the big triangle, at least one stick with number 33 lies in the interior of the big triangle. Thus all 1010 occurrences must be used. But the stick in the interior of the big triangle and having 33 on it is a side of another triangle entirely in the interior of the big triangle, whence we have 1111 occurrences of 33 when counted by triangles. The contradiction shows that the sum 2727 is impossible.

Any of Figures 25, 26, 27, 28 and 29 shows that the sum can be 2626.

*Remark:* Figures 24–29 contain all possibilities, modulo rotations and reflections, for obtaining the sum 2626.

Figure 3
Figure 4
Figure 5
Figure 6
Figure 7

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.