Maths Olympiad Prep

Library / /361 of 377

Algebra Difficulty 5.9 AIME, harder Prove it United States

Problem:
Let SS be the set of points (x,y,z)(x, y, z) in R3\mathbb{R}^3 such that x,yx, y, and zz are positive integers less than or equal to 100100. Let ff be a bijective map between SS and the {1,2,,1000000}\{1,2, \ldots, 1000000\} that satisfies the following property: if x1x2,y1y2x_1 \leq x_2, y_1 \leq y_2, and z1z2z_1 \leq z_2, then f(x1,y1,z1)f(x2,y2,z2)f\left(x_1, y_1, z_1\right) \leq f\left(x_2, y_2, z_2\right). Define
Ai=j=1100k=1100f(i,j,k),Bi=j=1100k=1100f(j,i,k), and Ci=j=1100k=1100f(j,k,i) \begin{aligned} A_i & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(i, j, k), \\ B_i & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(j, i, k), \\ \text{ and } C_i & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(j, k, i) \end{aligned}
Determine the minimum value of Ai+1Ai+Bj+1Bj+Ck+1CkA_{i+1}-A_i+B_{j+1}-B_j+C_{k+1}-C_k.

Solution

Solution:
We examine the 66 planes, their intersections and the lines between 22 points in one of the three pairs of parallel planes. The expression is equivalent to summing differences in values along all these lines. We examine the planes intersections. There is one cube, 3983 \cdot 98 squares and 398983 \cdot 98 \cdot 98 lines. The minimum value of the difference along a line is 11. For a square, to minimize the differences we take four consecutive numbers, and the minimum value is 66. To find the minimum value along a cube, we take 88 consecutive numbers. Since we are taking differences, we can add or subtract any constant to the numbers, so we assume the numbers are 11-88. Examining the cube, we see there's 11 spot where the number is multiplied by 3-3, 33 spots where the number is multiplied by 1-1, 11 spot where the number is multiplied by 33, and 33 spots where the number is multiplied by 11. 11 and 88 must go in the corners, and 2,3,4,52,3,4,5 must go in spots multiplied by 1,1,1,1-1,-1,1,1, respectively. To minimize the differences we put 55 in the final spot multiplied by 1-1, and 44 in the spot multiplied by 11 opposite 55. Then the sum of all the differences is 2828, so the minimum for a cube is 2828. So the answer is 28+18(1002)+3(1002)2=30000+600+1236+28=3060428+18(100-2)+3(100-2)^2=30000+600+12-36+28=30604. It is clear that this value can be obtained.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.