Third Millennium International Mathematical Olympiad 2009
Grade 9
Problem 4

None of the group of nine distinct natural numbers exceeds 16. Prove that, out of these nine, at least one divides at least one other.

Solution by Clement Lau, Temple City, CA.
Solution 2.

|Up| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

I will prove that any group of nine distinct natural numbers not exceeding 16 will include one number that divides another in the group by proving that it is impossible to have a group not having such a property.

If 1 is in the group, then it has the property described above, because 1 divides all natural numbers. Therefore, in order for a group to not have the property, 1 must not be in the group.

If 2 is in the group, then in order for the property above to not apply to the group, all the other numbers must be odd, because 2 divides all even numbers. There are not enough odd natural numbers less than 16 to fulfill the requirement of a group of nine distinct natural numbers. Therefore, in order for a group to not have the property, 2 must not be in the group.

If 3 is in the group, 6, 9, 12, and 15 must not be in the group. This leaves (in addition to 3) 4, 5, 7, 8, 10, 11, 13, 14, and 16. Here, we have 10 numbers. But, some of these numbers will have to be excluded, because some of these numbers divide each other. Either 5 or 10 will have to be excluded, because 5 divides 10. That leaves us 9 numbers. Also, 4 divides 8 and 16, so 4 will have to be excluded also. We could go on to eliminate more numbers in this group, but there is no need to, because we have only 8 numbers remaining. Therefore, in order for a group to not have the property, 3 must not be in the group.

If 4 is in the group, 8, 12, and 16 must not be in the group. This leaves (in addition to 4) 5, 6, 7, 9, 10, 11, 13, 14, and 15. Here, we have 10 numbers. Either 7 or 14 will have to be excluded, because 7 divide 14. That leaves 9 numbers. Also, 5 divides 10 and 15, so 5 will have to be excluded. We have only 8 numbers remaining. Therefore, in order for a group to not have the property, 4 must not be in the group.

If 5 is in the group, 10 and 15 must not be in the group. This leaves (in addition to 5) 6, 7, 8, 9, 11, 12, 13, 14, and 16. Here, we have 10 numbers. Either 7 or 14 will have to be excluded, because 7 divides 14. That leaves 9 numbers. Also, either 6 or 12 will have to be excluded, because 6 divides 12. We could go on to eliminate more numbers in this group, but there is no need to, because we have only 8 numbers remaining. Therefore, in order for a group to not have the property, 5 must not be in the group.

If 6 were in the group, 12 must not be in the group. This leaves (in addition to 6) 7, 8, 9, 10, 11, 13, 14, 15, and 16. Here, we have 10 numbers. Either 8 or 16 will have to be excluded, because 8 divides 16. That leaves 9 numbers. Also, either 7 or 14 will have to be excluded, because 7 divides 14. That leaves 8 numbers. Therefore, in order for a group to not have the property, 6 must not be in the group.

If 7 were in the group, 14 must not be in the group. This leaves (in addition to 7) 8, 9, 10, 11, 12, 13, 15, and 16. Here, we have 9 numbers. Either 8 or 16 will have to be excluded, because 8 divides 16. That leaves 8 numbers. Therefore, 7 must not be in the group.

If 8 were in the group, 16 must not be in the group. This leaves (in addition to 8) 9, 10, 11, 12, 13, 14, and 15. This is only 8 numbers. Therefore, 8 must not be in the group.

It has been proven that in order for a group to not have the above property, it must not include 1, 2, 3, 4, 5, 6, 7, or 8. This leaves 9, 10, 11, 12, 13, 14, 15, and 16. But, this is only 8 numbers. Therefore, it is impossible to have group of nine distinct natural numbers, none of which exceed 16, which does not include a number that divides another number in the group. This means that for any group of nine distinct numbers, none of which exceeds 16, at least one of the numbers divides another in the group.

|Up| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Let's solve a more general problem: In a group of n+1 numbers chosen from the set 1, 2, ..., 2n, at least one divides at least one other.

Any number K can be written as a product of a power of 2 (which may be 0) and an odd number: K = 2^sk, where k is odd and s ≥ 0. If there is another number, say M = 2^tk, with s ≠ t, then either K divides M (if s > t) or M divides K (if s < t).

Return to the given set of n+1 natural numbers, say, K₁, K₂, ..., K_n+1. Stripped of the powers of 2, the numbers become k₁, k₂, ..., k_n+1 which is the set of odd numbers below 2n. But below 2n there are only n odd number: 1, 3, ..., 2n - 1, implying that among the numbers k₁, k₂, ..., k_n+1 at least two are equal, say, k_i = k_j. These correspond to K_i and K_j out of the given set. By the previous paragraph, the smaller of the two divides the larger one.

Note: the assertion that allowed us to claim the existence of two equal numbers in the set k₁, k₂, ..., k_n+1, although simple, is extremely powerful. It is known as the pigeonhole or Dirichlet principle.

|Up| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny