Разделы 
Дополнительно
Задача по математике - 111
2014-06-07 
Запись числа $n \in \mathbf{N}$, кратного 17, в двоичной системе счисления содержит ровно 3 цифры 1. Доказать, что в этой записи содержится не менее 6 цифр 0, а если их ровно 7, то число $n$ является четным.
Решение:
Поскольку двоичная запись числа $n$, делящегося на 17, содержит ровно 3 цифры 1 (а остальные цифры - 0), то это число представляется в виде суммы
$n = 2^{k} + 2^{l} + 2^{m}$,
где числа $k, l, m \in \mathbf{Z}^{+}$ удовлетворяют неравенствам $k < l < m$. Пусть рассматриваемая двоичная запись содержит менее 6 цифр 0. Тогда $m \leq 7$ и соотношение
$n = 0 (mod 17)$
не пожег быть выполнено, поскольку числа вида $2^{i}$ при $i =0, 1, 2, 3, 4, 5, 6, 7$ сравнимы по модулю 17 с числами 1, 2, 4, 8. -1, -2, -4, -8 соответственно, и несложный перебор показывает, что сумма любых 3 различных чисел из последнего набора не делится на 17. Поэтому в двоичной записи числа $n$ имеется по меньшей мере 6 цифр 0. Если же их ровно 7, то $m = 9$. Тогда число $n$ не может быть нечетным, так как иначе $k = 0$ и
$2^{k} + 2^{m} = 3 (mod 17)$,
в то время как соотношение
$2^{l} = - 3 (mod 17)$
не выполнено ни при каких значениях
$l \in {1; \cdots ; 8}$.
Следовательно, в этом случае число $n$ является четным (оно действительно может делиться на 17. например, если $k = 1, l = 6, m = 9$).
Запись числа $n \in \mathbf{N}$, кратного 17, в двоичной системе счисления содержит ровно 3 цифры 1. Доказать, что в этой записи содержится не менее 6 цифр 0, а если их ровно 7, то число $n$ является четным.
Решение:
Поскольку двоичная запись числа $n$, делящегося на 17, содержит ровно 3 цифры 1 (а остальные цифры - 0), то это число представляется в виде суммы
$n = 2^{k} + 2^{l} + 2^{m}$,
где числа $k, l, m \in \mathbf{Z}^{+}$ удовлетворяют неравенствам $k < l < m$. Пусть рассматриваемая двоичная запись содержит менее 6 цифр 0. Тогда $m \leq 7$ и соотношение
$n = 0 (mod 17)$
не пожег быть выполнено, поскольку числа вида $2^{i}$ при $i =0, 1, 2, 3, 4, 5, 6, 7$ сравнимы по модулю 17 с числами 1, 2, 4, 8. -1, -2, -4, -8 соответственно, и несложный перебор показывает, что сумма любых 3 различных чисел из последнего набора не делится на 17. Поэтому в двоичной записи числа $n$ имеется по меньшей мере 6 цифр 0. Если же их ровно 7, то $m = 9$. Тогда число $n$ не может быть нечетным, так как иначе $k = 0$ и
$2^{k} + 2^{m} = 3 (mod 17)$,
в то время как соотношение
$2^{l} = - 3 (mod 17)$
не выполнено ни при каких значениях
$l \in {1; \cdots ; 8}$.
Следовательно, в этом случае число $n$ является четным (оно действительно может делиться на 17. например, если $k = 1, l = 6, m = 9$).
