Maths Olympiad Prep

Library / /3 of 37

Number theory Difficulty 6.2 National olympiad Find the answer

Find the smallest positive integer K K such that every K K-element subset of {1,2,...,50} \{1,2,...,50 \} contains two distinct elements a,b a,b such that a\plusb a\plus{}b divides ab ab.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the smallest positive integer K K such that every K K -element subset of {1,2,,50} \{1, 2, \ldots, 50\} contains two distinct elements a a and b b such that a+b a + b divides ab ab , we need to analyze the properties of the set and the divisibility condition.

Consider the set {1,2,,50} \{1, 2, \ldots, 50\} . We need to ensure that in any subset of size K K , there exist two elements a a and b b such that a+bab a + b \mid ab .

First, observe that if a a and b b are both even, then a+b a + b is even and ab ab is even, so a+b a + b divides ab ab . Similarly, if a a and b b are both odd, then a+b a + b is even and ab ab is odd, so a+b a + b does not necessarily divide ab ab .

To ensure that a+bab a + b \mid ab for any subset of size K K , we need to consider the worst-case scenario where no two elements a a and b b satisfy the condition. This happens when the subset contains numbers that do not pair well under the given condition.

By the Pigeonhole Principle, if we have more than 25 elements in the subset, there must be at least one pair of elements a a and b b such that a+b a + b divides ab ab , because there are only 25 possible sums a+b a + b that are less than or equal to 50.

Therefore, the smallest positive integer K K such that every K K -element subset of {1,2,,50} \{1, 2, \ldots, 50\} contains two distinct elements a a and b b such that a+b a + b divides ab ab is:

The answer is: 26\boxed{26}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.