Maths Olympiad Prep

Library / /37 of 53

Combinatorics Difficulty 6.9 National olympiad Prove it Vietnam

An investor has two rectangular lands, each of size 120×100120 \times 100.

a. On the first land, she wants to build a house with a rectangular base of size 25×3525 \times 35 and nine circular flower pots with diameter 55 outside the house. Prove that for all positions of the flower pots, the remaining land is still sufficient to build the desired house.

b. On the second land, she wants to construct a polygonal fish pond such that the distance from an arbitrary point on the land, outside the pond, to the nearest pond edge is not over 55. Prove that the perimeter of the pond is not smaller than 440−202440 - 20\sqrt{2}.

Solution

a.
Consider the rectangle ABCDABCD where AB=CD=120AB = CD = 120 and AD=BC=100AD = BC = 100. Divide the rectangle into 1010 sub-rectangles of size 30×4030 \times 40 as shown below. Consider 99 centers of the flower pots. By the pigeonhole principle, it is clear that there exists a sub-rectangle that does not contain any center.

Suppose that rectangle is XYZTXYZT where XY=ZT=40XY = ZT = 40, XT=YZ=30XT = YZ = 30. Consider one more rectangle X′Y′Z′T′X'Y'Z'T' lying inside XYZTXYZT such that the sides of two rectangles are pairwise parallel and the gaps are equal to 2.52.5.

Figure 1

It is easy to check that X′Y′Z′T′X'Y'Z'T' does not share any point with the pots so we can build a house on this plot.

b.
Consider a rectangle ABCDABCD where AB=CD=120AB = CD = 120 and AD=BC=100AD = BC = 100. Let LL be the perimeter of the lake. According to the problem, there exist points A′A', B′B', C′C', D′D' in LL such that
AA′, BB′, CC′, DD′≤5. AA',\ BB',\ CC',\ DD' \leq 5.
Since the lake is a convex polygon, then A′B′A'B', B′C′B'C', C′D′C'D' and D′A′D'A' do not overlap. Hence,
∣L∣≥A′B′+B′C′+C′D′+D′A′. |L| \geq A'B' + B'C' + C'D' + D'A'.
Denote A1A_1 as the projection of A′A' to ADAD and A2A_2 as the projection of A′A' to ABAB. Similarly, we can define B1B_1, B2B_2, C1C_1, C2C_2, D1D_1, D2D_2 and we have
A1A′+A′B′+B′B1≥A1B1≥AB=120. A_1A' + A'B' + B'B_1 \geq A_1B_1 \geq AB = 120.
Similarly, we also have
B2B′+B′C′+C′C2≥100, B_2B' + B'C' + C'C_2 \geq 100,
C1C′+C′D′+D′D1≥120, C_1C' + C'D' + D'D_1 \geq 120,
D2D′+D′A′+A′A2≥100. D_2D' + D'A' + A'A_2 \geq 100.
Hence,
A′B′+B′C′+C′D′+D′A′+(A′A1+A′A2+B′B1+B′B2+C′C1+C′C2+D′D1+D′D2)≥440. A'B' + B'C' + C'D' + D'A' + (A'A_1 + A'A_2 + B'B_1 + B'B_2 + C'C_1 + C'C_2 + D'D_1 + D'D_2) \geq 440.
Finally, applying the Cauchy-Schwarz inequality, we have
A′A1+A′A2≤2(A′A12+A′A22)=2A′A22≤52. A'A_1 + A'A_2 \leq \sqrt{2(A'A_1^2 + A'A_2^2)} = \sqrt{2A'A_2^2} \leq 5\sqrt{2}.
Similarly, we also have
B′B1+B′B2≤52,C′C1+C′C2≤52,D′D1+D′D2≤52. B'B_1 + B'B_2 \leq 5\sqrt{2}, \quad C'C_1 + C'C_2 \leq 5\sqrt{2}, \quad D'D_1 + D'D_2 \leq 5\sqrt{2}.
From these inequalities, it is clear that the length of LL does not exceed 440−202440 - 20\sqrt{2}. □\square

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.