Problem 1138

Solution. We know that a natural number is a square if and only if each prime number in its prime factorization appears an even number of times. The prime numbers in the set $Z = \{1, 2, 3, \ldots, 20\}$ form the set $P = \{2, 3, 5, 7, 11, 13, 17, 19\}$, and the remaining 12 numbers (1 and the composite numbers) form the set

$$Q = \{1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20\}$$

Since no square subset of the set $Z$ can consist entirely of elements from $P$, it must contain at least one number from $Q$.

Let's explain why, on the other hand, from the $2^{12} - 1$ non-empty subsets $X$ of the set $Q$, each can be uniquely supplemented with primes from $P$ to form a square set (or it is not necessary or possible to add any prime from $P$ if the set $X$ is already square). This follows from the fact that for a given non-empty subset $X \subseteq Q$, the supplementary primes from $P$ must be exactly those that appear an odd number of times in the prime factorization of the number equal to the product of the elements of $X$. The square sets thus created, in the number $2^{12} - 1$ (=4095), are clearly distinct (since each has a different intersection with the set $Q$), so the number of all square subsets of the set $Z$ is indeed equal to $2^{12} - 1$, as we were to prove.