# Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other.

Any help is appreciated!

-

## 1 Answer

HINT: Create a pigeonhole for each odd positive integer $2k+1<2n$, and put into it all numbers in $[2n]$ of the form $(2k+1)2^r$ for some $r\ge 0$.

-

Ok, so for any set S=(1, 2, ..., 2n), we choose all odd numbers from that S, so So=(1, 3,...,2k+1) such 2k+1 < 2n. For each element in S choose those that satisfy (2k+1)2^r, which are multiples of each element in So. Let this set be S2 = (2, 6,...,(2k+1)2^r), as long as (2k+1)2^r < 2n. S2 is necessarily bigger than So, and thus, each element in So can be 'mapped' to multiple multiples of itself. Consequently, any set bigger than S, of size n+1, must also have this property. Is this reasoning correct? – user64093 Feb 26 at 18:38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 11, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9038315415382385, "perplexity_flag": "head"}