# Thread:

1. ## Divisibility proof in random integer subset

Can anyone help me getting started on this one? I figure it has something to do with the pigeonhole principle, but I don't know where to start.

2. Originally Posted by knarQ
Can anyone help me getting started on this one? I figure it has something to do with the pigeonhole principle, but I don't know where to start.

We can prove a more general result. If $A$ is a subset with $n+1$ elements from $\{1,2,3,...,2n\}$ then there exists $a,b\in A$ with $a|b$. Each element in $\{1,2,...,2n\}$ can be written as $n\cdot 2^m$ where $n$ is odd and $m\geq 0$. Let these be our pigeonholes. We see that there are $n$ pigeonholes because there are $n$ odd numbers between $1,2,...,2n$. Thus, two numbers end up in the same pigeonhole. So $a=n\cdot 2^{m_1}, b=n\cdot 2^{m_2}$ not it is clear that $a|b$ if $m_1<m_2$.

3. It took me a while to get this but it's a really nice proof. I was thinking in the lines of odd numbers and multiples of odd numbers but i couldn't get it down on paper, so thank you very much!

#### Search Tags

View Tag Cloud

Copyright © 2005-2013 Math Help Forum. All rights reserved.
{"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": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 15, "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": false}, "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.9708643555641174, "perplexity_flag": "head"}