Maths Olympiad Prep

Library / /57 of 57

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Russia

A straight stick of length 22 m is cut into NN pieces, the length of each (measured in centimeters) is an integer number. Find the least value of NN such that it is always possible to make a rectangular contour using all the obtained pieces. (It is not allowed to break the pieces.)

Прямую палку длиной 22 метра распилили на NN палочек, длина каждой из которых выражается целым числом сантиметров. При каком наименьшем NN можно гарантировать, что, использовав все получившиеся палочки, можно, не ломая их, сложить контур некоторого прямоугольника?

Solution

Answer: N=102N = 102.

First solution. Suppose N101N \leq 101. Cut the stick into N1N-1 pieces of length 11 cm and one piece of length (201N)(201 - N) cm. From this set, it is impossible to form a rectangle, since each side of the rectangle is less than the semiperimeter, and therefore the piece of length 201N100201 - N \geq 100 cm cannot be part of any side. Thus, N102N \geq 102.

Let us show that for N=102N = 102 it is possible to form a rectangle. For this, note that among all the pieces there will be two of length 11 cm. Indeed, if this were not the case, the total length of the pieces would be at least 2101+1=2032 \cdot 101 + 1 = 203 cm, which is not true.

Set aside these two pieces. Let the lengths of the remaining pieces be a1,a2,,a100a_1, a_2, \dots, a_{100} cm, then a1+a2++a100=198a_1 + a_2 + \dots + a_{100} = 198. Among the 100100 numbers A1=a1,A2=a1+a2,A3=a1+a2+a3,,A100=a1+a2++a100A_1 = a_1, A_2 = a_1 + a_2, A_3 = a_1 + a_2 + a_3, \dots, A_{100} = a_1 + a_2 + \dots + a_{100}, there will be two with the same remainder when divided by 9999. Let these be AkA_k and AA_\ell, k<k < \ell. The number AAkA_\ell - A_k is strictly greater than zero and strictly less than 198198, and it is divisible by 9999. Therefore, AAk=99=ak+1+ak+2++aA_\ell - A_k = 99 = a_{k+1} + a_{k+2} + \dots + a_\ell.

Thus, we have found several pieces with a total length of 9999 cm. Set these aside as well. The remaining pieces also have a total length of 9999 cm. Therefore, we can form a rectangle of 1×991 \times 99 cm.

Second solution. Here is another proof that for N=102N = 102 it is possible to form a rectangle.

Let the lengths of the pieces, in centimeters, be a1,a2,,a102a_1, a_2, \dots, a_{102}. We have a1+a2++a102=200a_1 + a_2 + \dots + a_{102} = 200. Consider a circle of length 200200 and mark 102102 red points dividing it into arcs of lengths a1,a2,,a102a_1, a_2, \dots, a_{102}. These points are some 102102 vertices of a regular 200200-gon TT inscribed in this circle. The vertices of TT are divided into pairs of opposite points. There are 100100 such pairs, and 102102 red points, so among the red points there are two pairs of opposite points.

These two pairs of points divide the circle into two pairs of equal arcs. Thus, we have divided all the pieces into four groups A,B,C,DA, B, C, D, with the total lengths in groups AA and CC, and in groups BB and DD, being equal. Therefore, we can form a rectangle, using each group to make one side.

Third solution. Here is yet another proof that for N=102N = 102 it is possible to form a rectangle. We show how to lay out a rectangle 1×991 \times 99.

Let 2\ell \geq 2 be the largest among the lengths of all the pieces. Let xx be the number of pieces of length 11. Then, besides these xx pieces and the piece of length \ell, there are 101x101 - x pieces, each of length at least 22. Hence +x+2(101x)200\ell + x + 2(101 - x) \leq 200, and x+2x \geq \ell + 2. So, there are at least +2\ell + 2 pieces of length 11. Set aside two pieces of length 11—use them to make two sides of the rectangle, leaving \ell pieces of length 11.

Start laying out the pieces in order of decreasing length to form one side of length 9999. Suppose at some step the row has length L<99L < 99, and after adding the next piece of length mm it becomes L+m>99L + m > 99. Then remove the last piece of length mm, and instead place 99L99 - L pieces of length 11 (this can be done since 99L<m99 - L < m \leq \ell). Now we have three sides of the rectangle (11, 11, and 9999). Laying out the remaining pieces in a row, we get another side of length 9999.

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.