Maths Olympiad Prep

Library / /36 of 62

Number theory Difficulty 5.8 AIME, harder Prove it Ukraine

Olesya chose 5 numbers from the set {1;2;3;4;5;6;7}\{1; 2; 3; 4; 5; 6; 7\}. She told Pavlik the product of these numbers and asked whether the sum of these numbers is odd or even. Pavlik replied that he could not determine it for sure. What product might have had Olesya?

Solution

If Pavlik knows the product, he could determine the product of the last two numbers that were not chosen. Since he could not determine the pairing of the product, then he could not determine the numbers that were not chosen although he knows their product. Consider all products of two numbers in the given set:
12=2,13=3,14=4,15=5,16=6,17=7,23=6,24=8,25=10,26=12,27=14,34=12,35=15,36=18,37=21,45=20,46=24,47=28,56=30,57=35,67=42. \begin{aligned} 1 \cdot 2 &= 2, \quad 1 \cdot 3 = 3, \quad 1 \cdot 4 = 4, \quad 1 \cdot 5 = 5, \quad 1 \cdot 6 = 6, \quad 1 \cdot 7 = 7, \quad 2 \cdot 3 = 6, \quad 2 \cdot 4 = 8, \\ 2 \cdot 5 &= 10, \quad 2 \cdot 6 = 12, \quad 2 \cdot 7 = 14, \quad 3 \cdot 4 = 12, \quad 3 \cdot 5 = 15, \quad 3 \cdot 6 = 18, \quad 3 \cdot 7 = 21, \\ 4 \cdot 5 &= 20, \quad 4 \cdot 6 = 24, \quad 4 \cdot 7 = 28, \quad 5 \cdot 6 = 30, \quad 5 \cdot 7 = 35, \quad 6 \cdot 7 = 42. \end{aligned}
There are only 2 products that appear more than once. This is 16=6=231 \cdot 6 = 6 = 2 \cdot 3 and 26=12=342 \cdot 6 = 12 = 3 \cdot 4. Suppose that the product of the two numbers that were not chosen equals 66. In both cases the sum of the numbers is odd: 1+6=71+6=7 and 2+3=52+3=5. Thus the sum of chosen numbers is also odd. This contradicts Pavlik's claim. Therefore, the product of the two numbers that were not chosen might equal 1212. In this case their sum might be even (2+6=82+6=8) or odd (3+4=73+4=7). Then the product of 5 chosen numbers is equal to 123456712=420\frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7}{12} = 420.

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.