Maths Olympiad Prep

Library / /770 of 860

Combinatorics Difficulty 5.5 AIME, harder Find the answer

For each positive real number α\alpha, define αN:={αmmN} \lfloor\alpha \mathbb{N}\rfloor:=\{\lfloor\alpha m\rfloor \mid m \in \mathbb{N}\} Let nn be a positive integer. A set S{1,2,,n}S \subseteq\{1,2, \ldots, n\} has the property that: for each real β>0\beta>0,  if SβN, then {1,2,,n}βN \text { if } S \subseteq\lfloor\beta \mathbb{N}\rfloor \text {, then }\{1,2, \ldots, n\} \subseteq\lfloor\beta \mathbb{N}\rfloor Determine, with proof, the smallest possible size of SS.

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

Solution

Answer: n/2+1\lfloor n / 2\rfloor+1 Solution: For each k{n/2,,n}k \in\{\lceil n / 2\rceil, \ldots, n\}, picking β=1+1/k\beta=1+1 / k gives βN[n]=[n]\{k} \lfloor\beta \mathbb{N}\rfloor \cap[n]=[n] \backslash\{k\} so SS must contain kk. Now we show that S={n/2,,n}S=\{\lceil n / 2\rceil, \ldots, n\} works; this set SS has n/2+1\lfloor n / 2\rfloor+1 elements. Suppose β\beta satisfy SβNS \subseteq\lfloor\beta \mathbb{N}\rfloor, and suppose for the sake of contradiction that [n]⊄βN[n] \not \subset\lfloor\beta \mathbb{N}\rfloor. Since we may increase β\beta by a small amount ε\varepsilon without affecting βN[n]\lfloor\beta \mathbb{N}\rfloor \cap[n], we may assume β\beta is irrational. Let α\alpha satisfy 1/α+1/β=11 / \alpha+1 / \beta=1. By Beatty's Theorem, αN\lfloor\alpha \mathbb{N}\rfloor and βN\lfloor\beta \mathbb{N}\rfloor are complement sets in N\mathbb{N}. Let mm be the maximal element of [n][n] that is not in βN\lfloor\beta \mathbb{N}\rfloor. Then m=kαm=\lfloor k \alpha\rfloor for some integer kk. Consider m=2kα{2m,2m+1}m^{\prime}=\lfloor 2 k \alpha\rfloor \in\{2 m, 2 m+1\}, which must be an element of αN\lfloor\alpha \mathbb{N}\rfloor. Clearly, m>mm^{\prime}>m, and since m<n/2m<n / 2, mnm^{\prime} \leqslant n, so mm^{\prime} is also an element of [n][n] that is not in βN\lfloor\beta \mathbb{N}\rfloor. This contradicts the maximality of mm, and we are done.

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.