Разделы 
Дополнительно
Задача по математике - 92
2014-06-07 
На числовой оси взят интервал длины $1/n (n \in \mathbf{N})$. Доказать, что в этом интервале содержится не более $(n+1)/2$ несократимых дробей вида $p/q$, где $p,q \in \mathbf{Z}, 1 \leq 7 \leq n$.
Решение:
Предположим, что, вопреки утверждению задачи, в некотором интервале длины $1/n$ содержится более $(n + 1)/2$ несократимых дробей вида $p/q$, где $q \in {1; 2; \cdots ; n}$. Докажем, что среди знаменателей этих дробей найдутся два, один из которых делится на другой. Действительно, представим каждый из знаменателей в виде $2^{r}s$, где $s$ - нечетное число, $r \in \mathbf{Z}^{+}$. Количество различных нечетных чисел среди чисел $1, 2, \cdots, n$ равно $[(n+1)/2]$ (т. е. меньше, чем количество рассматриваемых знаменателей), следовательно, найдутся два знаменателя
$q=2^{r} \cdot s$ и $q_{1}=2^{r_{1}} \cdot s_{1}$,
для которых $s=s_{1}$ и $ r \leq r_{1}$. Тогда одни из них делится на другой, т. е. $q_{1} = kq$. Таким образом, среди дробей можно выбрать два различных числа вида $m/q$ и $l/kq$ где $kq \leq n$. Тогда
$\left | \frac{m}{q} - \frac{l}{kq} \right | < \frac{1}{n}$,
так как оба числа лежат в интервале длины $1/n$. Поэтому $km – l = 0$, ибо в противном случае
$\left | \frac{m}{q} - \frac{l}{kq} \right | = \frac{|km - l|}{kq} \geq \frac{1}{kq} \geq \frac{1}{n}$.
Итак,
$km=l$ и $l/kq=km/kq=m/q$,
т. е. оба выбранных числа совпадают. Полученное противоречие доказывает утверждение задачи.
На числовой оси взят интервал длины $1/n (n \in \mathbf{N})$. Доказать, что в этом интервале содержится не более $(n+1)/2$ несократимых дробей вида $p/q$, где $p,q \in \mathbf{Z}, 1 \leq 7 \leq n$.
Решение:
Предположим, что, вопреки утверждению задачи, в некотором интервале длины $1/n$ содержится более $(n + 1)/2$ несократимых дробей вида $p/q$, где $q \in {1; 2; \cdots ; n}$. Докажем, что среди знаменателей этих дробей найдутся два, один из которых делится на другой. Действительно, представим каждый из знаменателей в виде $2^{r}s$, где $s$ - нечетное число, $r \in \mathbf{Z}^{+}$. Количество различных нечетных чисел среди чисел $1, 2, \cdots, n$ равно $[(n+1)/2]$ (т. е. меньше, чем количество рассматриваемых знаменателей), следовательно, найдутся два знаменателя
$q=2^{r} \cdot s$ и $q_{1}=2^{r_{1}} \cdot s_{1}$,
для которых $s=s_{1}$ и $ r \leq r_{1}$. Тогда одни из них делится на другой, т. е. $q_{1} = kq$. Таким образом, среди дробей можно выбрать два различных числа вида $m/q$ и $l/kq$ где $kq \leq n$. Тогда
$\left | \frac{m}{q} - \frac{l}{kq} \right | < \frac{1}{n}$,
так как оба числа лежат в интервале длины $1/n$. Поэтому $km – l = 0$, ибо в противном случае
$\left | \frac{m}{q} - \frac{l}{kq} \right | = \frac{|km - l|}{kq} \geq \frac{1}{kq} \geq \frac{1}{n}$.
Итак,
$km=l$ и $l/kq=km/kq=m/q$,
т. е. оба выбранных числа совпадают. Полученное противоречие доказывает утверждение задачи.
