Разделы 
Дополнительно
Задача по математике - 2912
2019-05-06 
Пусть $t$ - произвольное положительное число; число несократимых дробей $\frac{p}{q}$, числитель $p$ и знаменатель $q$ которых не превосходят $t$, обозначим через $d(t)$.
Чему равна сумма $S = d \left ( \frac{100}{1} \right ) + d \left ( \frac{100}{2} \right ) + d \left ( \frac{100}{3} \right ) + \cdots + d \left ( \frac{100}{99} \right ) + d \left ( \frac{100}{100} \right )$?
Решение:
Каждой несократимой дроби $\frac{p}{q}$, где
$0 < p \leq 100$, $0 < q \leq 100$,
сопоставим точку $M$ с координатами $p$, $q$; при этом неравенства (*) указывают, что точка $M$ расположена внутри заштрихованного на рис. квадрата $H = OACB$, ограниченного осями координат и прямыми $x = 100$ и $у = 100$ (или, в крайнем случае, $M$ принадлежит стороне $АС$ или стороне $BC$ квадрата $H$), а несократимость дроби $\frac{p}{q}$ означает, что на отрезке $ОМ$ нет никаких отличных от $M$ «целых» точек (точек с целыми координатами: в самом деле, равенства $p = kp_1, q = kq_1$ указывающие, что дробь - можно сократить на $k$, означают, что отрезку $ОМ$ принадлежит также целая точка $M_1(p_1q_1)$. При этом если высекаемый квадратом $H$ на проходящей через $О$ прямой $l$ отрезок $OP$ содержит $A$ целых точек $(p_0, q_0), (2p_0, 2q_0), (3p_0, 3q_0), \cdots, (np_0, nq_0)$ (где $M_0 (p_0, q_0)$ - самая близкая к $О$ из этих точек), то (поскольку $np_0 \leq 100$, $nq_0 \leq 100$) имеем $p_0 \leq \frac{100}{n} \left ( < \frac{100}{n-1} < \frac{100}{n-2} < \cdots < \frac{100}{1} \right )$ и $q_0 \leq \frac{100}{n} \left ( < \frac{100}{n-1} < \frac{100}{n-2} < \cdots < \frac{100}{1} \right )$ и, значит несократимая дробь $\frac{p_0}{q_0}$ учитывается в слагаемых $d \left ( \frac{100}{1} \right ), d \left ( \frac{100}{2} \right ), \cdots, d \left ( \frac{100}{n} \right )$, суммы $S$, т. е. всего участвует в этой сумме $n$ раз (а сократимые дроби $\frac{2p_0}{2q_0}, \frac{3p_0}{3q_0}, \cdots, \frac{np_0}{nq_0},$, разумеется, вообще не учитываются в сумме $S$). Таким образом, вклад дроби $\frac{p_0}{q_0},$ в сумму $S$ равен $n$, т. е. равен числу целых точек на отрезке $OP$.
Из доказанного следует, что общее число учитываемых в сумме $S$ дробей - т. е. численное значение суммы $S$ - равно полному числу всех целых точек в квадрате $H$, т. е. $S = 100 \cdot 100 = 10000$.
Пусть $t$ - произвольное положительное число; число несократимых дробей $\frac{p}{q}$, числитель $p$ и знаменатель $q$ которых не превосходят $t$, обозначим через $d(t)$.
Чему равна сумма $S = d \left ( \frac{100}{1} \right ) + d \left ( \frac{100}{2} \right ) + d \left ( \frac{100}{3} \right ) + \cdots + d \left ( \frac{100}{99} \right ) + d \left ( \frac{100}{100} \right )$?
Решение:
Каждой несократимой дроби $\frac{p}{q}$, где
$0 < p \leq 100$, $0 < q \leq 100$,
сопоставим точку $M$ с координатами $p$, $q$; при этом неравенства (*) указывают, что точка $M$ расположена внутри заштрихованного на рис. квадрата $H = OACB$, ограниченного осями координат и прямыми $x = 100$ и $у = 100$ (или, в крайнем случае, $M$ принадлежит стороне $АС$ или стороне $BC$ квадрата $H$), а несократимость дроби $\frac{p}{q}$ означает, что на отрезке $ОМ$ нет никаких отличных от $M$ «целых» точек (точек с целыми координатами: в самом деле, равенства $p = kp_1, q = kq_1$ указывающие, что дробь - можно сократить на $k$, означают, что отрезку $ОМ$ принадлежит также целая точка $M_1(p_1q_1)$. При этом если высекаемый квадратом $H$ на проходящей через $О$ прямой $l$ отрезок $OP$ содержит $A$ целых точек $(p_0, q_0), (2p_0, 2q_0), (3p_0, 3q_0), \cdots, (np_0, nq_0)$ (где $M_0 (p_0, q_0)$ - самая близкая к $О$ из этих точек), то (поскольку $np_0 \leq 100$, $nq_0 \leq 100$) имеем $p_0 \leq \frac{100}{n} \left ( < \frac{100}{n-1} < \frac{100}{n-2} < \cdots < \frac{100}{1} \right )$ и $q_0 \leq \frac{100}{n} \left ( < \frac{100}{n-1} < \frac{100}{n-2} < \cdots < \frac{100}{1} \right )$ и, значит несократимая дробь $\frac{p_0}{q_0}$ учитывается в слагаемых $d \left ( \frac{100}{1} \right ), d \left ( \frac{100}{2} \right ), \cdots, d \left ( \frac{100}{n} \right )$, суммы $S$, т. е. всего участвует в этой сумме $n$ раз (а сократимые дроби $\frac{2p_0}{2q_0}, \frac{3p_0}{3q_0}, \cdots, \frac{np_0}{nq_0},$, разумеется, вообще не учитываются в сумме $S$). Таким образом, вклад дроби $\frac{p_0}{q_0},$ в сумму $S$ равен $n$, т. е. равен числу целых точек на отрезке $OP$.
Из доказанного следует, что общее число учитываемых в сумме $S$ дробей - т. е. численное значение суммы $S$ - равно полному числу всех целых точек в квадрате $H$, т. е. $S = 100 \cdot 100 = 10000$.
