2022 SSMO Team Round Problems/Problem 6

Problem

Let $n$ be a positive integer, and let $x$ be some variable. Define $P_{x,n}$ as the maximum fraction of elements in the set of the first $x$ natural numbers that may be contained in a subset $S$ such that if $k$ is an element of $S$ , then $nk$ is not. For example, $P_{3, 3}=\frac{2}{3}$ , since we take the set $\{1, 2\}$ . As $x$ approaches infinity, $P_{x,n}$ approaches a value $P_n$ . Given that ${\prod_{n=2}^{100}P_n}=\frac{a}{b},$ where $a$ and $b$ are relatively prime positive integers, find $a+b.$

Solution

$\bold{CLAIM}$ : $P_n = \frac{n}{n+1}$

We maximize the number of elements in our subset by working from the highest elements to the lowest number of elements. Working through some numbers, we observe that the strategy is to first pick the top $\frac{n-1}{n}$ numbers, and then skip the next $\frac{n-1}{n^2}$ numbers, and then choose the next $\frac{n-1}{n^3}$ numbers and so on.

For example, working through $P_{64,2}$ , in order to maximize our set, we choose $(33,34,...,63,64)$ , then $(9,10,...,15,16)$ , then $(3,4)$ , and lastly $1$ . This follows the procedure above to maximize the number of elements in the set.

Therefore, we get $P_n = \frac{n-1}{n} + \frac{n-1}{n^3} + \frac{n-1}{n^5} + ...$ which evaluates to our claim above.

From this claim, we have that $\prod_{n=2}^{100} P_n = \frac{2}{101}$ so our answer is $2+101 = \boxed{103}$ x

-Vivdax

Page

Toolbox

Search

2022 SSMO Team Round Problems/Problem 6

Problem

Solution