Problem 1

Let

S

be a set of 9 distinct integers all of whose prime factors are at most 3. Prove that

S

contains 3 distinct integers whose product is a perfect cube.

Step 5 of 6: Find three boxes in distinct rows and columns

Previous step Next step

9\text{ elements in a }3\times3\text{ array }\Longrightarrow\text{three occupied boxes with distinct rows and columns}

Detailed analysis

Since there are nine elements and each box contains at most two, at least five boxes are occupied. With no row or column containing all three boxes, an elementary 3 by 3 array argument gives three occupied boxes in distinct rows and distinct columns. Choosing one element from each box gives types $(i_1,j_1),(i_2,j_2),(i_3,j_3)$ with both coordinate sets equal to $\{0,1,2\}$ , hence their sum is $(0,0)$ .