6. On the board, there are several natural numbers from 1 to 100, none of which is divisible by a two-digit prime number, and the product of any two of them is not a square of a natural number.

(a) Determine the largest possible number of numbers on the board.

(b) Determine the largest possible sum of the numbers on the board.

(Jaromír Šimša)
SOLUTION. Each number written on the board has a unique prime factorization $n=2^{a} \cdot 3^{b} \cdot 5^{c} \cdot 7^{d}$, where $a, b, c, d$ are suitable non-negative integers. According to the parity of the numbers in the quadruple $(a, b, c, d)$, we introduce the "type" of the number $n$ as a quadruple $(A, B, C, D)$, where each letter is either the letter $S$ (symbol for an even number) or the letter $L$ (symbol for an odd number). For example, the number $60 \mathrm{~s}$ with the factorization $2^{2} \cdot 3^{1} \cdot 5^{1} \cdot 7^{0}$ is of type $(S, L, L, S)$.

Let us realize that a natural number is a perfect square if and only if each prime number in its prime factorization has an even exponent. Such exponents in the prime factorization of the product $A \cdot B$ are precisely those of the numbers $A$ and $B$ on the board that are of the same type. Therefore, the condition of the problem for the products of pairs of numbers is satisfied if and only if every two numbers written on the board have different types.

Both tasks will be solved simultaneously. In the first one, we need to determine the largest number of numbers that can be written on the board. According to the previous paragraph, the answer is equal to the number of those types $(A, B, C, D)$ that have representatives among the numbers from 1 to 100. These will likely be precisely those types whose smallest representative does not exceed 100.

There are clearly $2^{4}=16$ types $(A, B, C, D)$. For each of them, we will first determine the smallest number of that type. It will certainly be the number $k=2^{a} \cdot 3^{b} \cdot 5^{c} \cdot 7^{d}$, where the smallest possible exponents $a, b, c, d \in\{0,1\}$ are chosen according to the quadruple of symbols $(A, B, C, D)$ - see the first two columns of the table below. The table is missing the types $(S, L, L, L)$ and $(L, L, L, L)$, because for them the smallest representatives $k=3 \cdot 5 \cdot 7=105$ and $k=2 \cdot 3 \cdot 5 \cdot 7=210$ are greater than 100. Thus, we find that the largest possible number of numbers on the board is $16-2=14$. (An example is the 14 values of $k$ from the table.)

| $(S, S, S, S)$ | $k=1$ | $K=10^{2}=100$ |
| :--- | :--- | :--- |
| $(L, S, S, S)$ | $k=2$ | $K=2 \cdot 7^{2}=98$ |
| $(S, L, S, S)$ | $k=3$ | $K=3 \cdot 5^{2}=75$ |
| $(S, S, L, S)$ | $k=5$ | $K=5 \cdot 4^{2}=80$ |
| $(S, S, S, L)$ | $k=7$ | $K=7 \cdot 3^{2}=63$ |
| $(L, L, S, S)$ | $k=2 \cdot 3=6$ | $K=6 \cdot 4^{2}=96$ |
| $(L, S, L, S)$ | $k=2 \cdot 5=10$ | $K=10 \cdot 3^{2}=90$ |
| $(L, S, S, L)$ | $k=2 \cdot 7=14$ | $K=14 \cdot 2^{2}=56$ |
| $(S, L, L, S)$ | $k=3 \cdot 5=15$ | $K=15 \cdot 2^{2}=60$ |
| $(S, L, S, L)$ | $k=3 \cdot 7=21$ | $K=21 \cdot 2^{2}=84$ |
| $(S, S, L, L)$ | $k=5 \cdot 7=35$ | $K=35$ |
| $(L, L, L, S)$ | $k=2 \cdot 3 \cdot 5=30$ | $K=30$ |
| $(L, L, S, L)$ | $k=2 \cdot 3 \cdot 7=42$ | $K=42$ |
| $(L, S, L, L)$ | $k=2 \cdot 5 \cdot 7=70$ | $K=70$ |

The second task is to determine the largest possible sum of the numbers on the board. We will likely get it by finding the largest representative $K$ of each of the 14 possible types among the numbers from 1 to 100, and then summing these 14 values of $K$. For each type, however, we already know its smallest representative $k$, so the first ten* smallest numbers of this type certainly have the form

$$
k, 2^{2} \cdot k, 3^{2} \cdot k, 4^{2} \cdot k, \ldots, 10^{2} \cdot k .
$$

The number $K$ will thus be determined as the largest of them that does not exceed 100, and then we will write it in the third column of the table for each type.

As we have already mentioned, the table lists only 14 of the 16 possible types. The numbers of the remaining two types $(S, L, L, L)$ and $(L, L, L, L)$ cannot be written on the board, because for the product of the three necessarily represented primes 3, 5, and 7, we have $3 \cdot 5 \cdot 7=105>100$. The answer to part a) of the problem is: The largest possible number of numbers written on the board is 14.

To achieve the largest sum of the numbers written on the board, we need to sum the largest permissible numbers from each of the 14 possible types, which we have written in the right column of the table. From this, the answer to part b) of the problem follows: The largest possible sum of the numbers written on the board is

$$
100+98+75+80+63+96+90+56+60+84+35+30+42+70=979 .
$$

SUPPLEMENTARY AND ADDITIONAL PROBLEMS:

N1. What is the largest number of numbers that can be selected from the set $\{1,2, \ldots, 2019\}$ such that the product of no three of the selected numbers is divisible by nine? Provide an example of a suitable subset and explain why it cannot have fewer elements. [68-C-S-1]

N2. What is the smallest possible sum of four natural numbers such that pairs formed from these numbers have the greatest common divisors $2,3,4,5,6$ and 9? Provide an example of a suitable quadruple with such a sum and explain why there does not exist a suitable quadruple with a smaller sum. [68-C-II-2][^0]

[^0]: * The eleventh number $12^{2} \cdot k$ will not be needed in our solution for any of the 14 possible types, as $10^{2} \cdot k$ is already greater than 100 for any $k>1$.