Competition problem — Number theory

Number theory Difficulty 5.3 AIME, harder Prove it Greece

We color the numbers $1, 2, 3, \ldots, 20$ with two colors, white and blank, in such a way that both colors are used. Find the number of ways we can perform this coloring if the product of white numbers and the product of blank numbers have maximal common divisor equal to $1$ . (P. Bregiannis)

Solution

Number $1$ can be colored in two ways, white or blank. Number $2$ also can be colored white or blank. Then all even numbers $2, 4, 6, 8, 10, 12, 14, 16, 18, 20$ have to be colored with the color of $2$ .
Also all numbers having common divisor greater than $1$ with the above numbers must be colored with the color of $2$ . The remaining numbers greater than $10$ , that is, $11, 13, 17, 19$ can be colored in two ways. Therefore the coloring can be made with $2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^6 = 64$ different ways. However we must delete the two cases we color all numbers white or blank. So we have finally $62$ different ways.

Looking for a route rather than 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.