Чётность · Целые числа

Всего задач: 9
Сброс
ARMO 2017, школьный этап, 10.2
ID: 42 🏷 ARMO 📅 2017 🎓 10 ★★★★☆☆☆☆☆☆ Легко
combinatorics number theory divisibility modular arithmetic pairing

Можно ли все натуральные числа от 1 до 800 разбить на пары так, чтобы сумма любой пары чисел делилась на 6?

Нельзя.

Для того чтобы сумма двух чисел делилась на 6, их остатки по модулю 6 должны быть взаимодополняющими до 6. Возможные пары остатков:

  • 0 и 0,
  • 1 и 5,
  • 2 и 4,
  • 3 и 3.

Таким образом, все числа, дающиеся на 6 (остаток 0), могут быть состыкованы только друг с другом. Значит, количество таких чисел должно быть чётным. Но в отрезке от 1 до 800 чисел, делящихся на 6, ровно ⌊800/6⌋ = 133 (это числа 6, 12, ..., 798). 133 — нечётное, поэтому нельзя разбить все 800 чисел на пары с требуемым свойством.

ARMO 2018, муниципальный этап, 11.4
ID: 43 🏷 ARMO 📅 2018 🎓 11 ★★★★★☆☆☆☆☆ Средне
divisibility geometry number theory parity polygons integers

В вершинах семнадцатиугольника записаны различные целые числа (по одному в каждой вершине). Затем все числа одновременно заменили на новые: каждое число заменили на разность двух следующих за ним по часовой стрелке чисел (из соседнего вычитали следующее за ним). Могло ли произведение полученных чисел оказаться нечётным?

Нет.

Пусть по кругу стояли числа \(a_1, a_2, \, \ldots, \, a_{17}\). Тогда новые числа будут равны \(a_2 - a_3, a_3 - a_4, \, \ldots, \, a_{17} - a_1, a_1 - a_2\), и их сумма равна 0.

Если сумма 17 чисел чётная, то среди них есть хотя бы одно чётное число (сумма нечётного количества нечётных чисел нечётна). Тогда произведение этих чисел чётно.

Ответ: Нет.

ARMO 2013, региональный этап, 10.1
ID: 46 🏷 ARMO 📅 2013 🎓 10 ★★★★★☆☆☆☆☆ Средне
number theory digits parity contradiction

Даны натуральные числа M и N, большие десяти, состоящие из одинакового количества цифр и такие, что M = 3N. Чтобы получить число M, надо в числе N к одной из цифр прибавить 2, а к каждой из остальных цифр прибавить по нечётной цифре. Какой цифрой могло оканчиваться число N?

Цифрой 6.

Число A = M – N = 2N чётно. Но, по условию, число A составлено из нечётных цифр и двойки. Значит, A оканчивается на 2. Поэтому вдвое меньшее число N оканчивается либо на 1, либо на 6.

Если N оканчивается на 1, то при его удвоении не происходит переноса десятка из последнего в предпоследний разряд. Значит, предпоследняя цифра числа A = 2N будет чётной, а она должна быть нечётной. Противоречие.

ARMO 2010, региональный этап, 10.1
ID: 45 🏷 ARMO 📅 2010 🎓 10 ★★★★★☆☆☆☆☆ Средне
combinatorics parity number theory circular arrangement proof contradiction

Незнайка выписал по кругу 11 натуральных чисел. Для каждых двух соседних чисел он посчитал их разность (из большего вычел меньшее). В результате среди найденных разностей оказалось четыре единицы, четыре двойки и три тройки. Докажите, что Незнайка где-то допустил ошибку.

Незнайка допустил ошибку, так как сумма разностей не может быть чётной.

Запишем каждую из наших разностей со знаком плюс, если в соответствующей паре чисел большее стоит перед меньшим по часовой стрелке, и со знаком минус в противном случае. У нас получились 11 разностей между числом и следующим за ним по часовой стрелке; значит, сумма всех этих чисел равна нулю, то есть чётна. Но это невозможно, поскольку среди них ровно семь нечётных чисел.

ARMO 2006, районный этап, 9.5
ID: 44 🏷 ARMO 📅 2006 🎓 9 ★★★★★☆☆☆☆☆ Средне
parity number theory combinatorics problem solving

На доске записано произведение \(a_1a_2\ldots a_{100}\), где \(a_1, \ldots, a_{100}\) – натуральные числа. Рассмотрим 99 выражений, каждое из которых получается заменой одного из знаков умножения на знак сложения. Известно, что значения ровно 32 из этих выражений чётные. Какое наибольшее количество чётных чисел среди \(a_1, a_2, \ldots, a_{100}\) могло быть?

33 числа.

Рассмотрим самое левое чётное число \(a_i\) и самое правое чётное число \(a_k\). Заметим, что чётными являются все суммы с номерами от \(i\) до \(k - 1\) и только они (в суммах с меньшими номерами первое слагаемое нечётно, а второе чётно; в суммах с большими номерами – наоборот).

Таким образом, \(k - i = 32\). Количество чётных чисел будет наибольшим, если все числа между \(a_i\) и \(a_k\) также чётны. В этом случае количество чётных чисел будет равно 33.

ARMO 2011, региональный этап, 10.3
ID: 48 🏷 ARMO 📅 2011 🎓 10 ★★★★★★☆☆☆☆ Средне
combinatorics number theory parity sums digits

Даны различные натуральные числа \( a_1, a_2, \, \ldots, \, a_{14} \). На доске выписаны все 196 чисел вида \( a_k + a_l \), где \( 1 \leq k, l \leq 14 \). Может ли оказаться, что для каждой комбинации из двух цифр среди написанных на доске чисел найдётся хотя бы одно число, оканчивающееся на эту комбинацию (то есть найдутся числа, оканчивающиеся на 00, 01, 02, \(\ldots\), 99 )?

Не может.

Пусть среди наших 14 чисел есть \( a \) чётных и \( b = 14 - a \) нечётных. Нечётное число на доске может появиться лишь как сумма чётного и нечётного, то есть таких чисел будет \( ab \) (при этом каждое будет выписано по два раза). Но \( 4ab \leq (a + b)^2 = 4 \cdot 49 \). Значит, на доске будет не более 49 различных нечётных чисел; а, чтобы выполнялось условие, их должно быть хотя бы 50.

ARMO 2007, заключительный этап, 9.2
ID: 47 🏷 ARMO 📅 2007 🎓 9 ★★★★★★☆☆☆☆ Средне
fractions parity combinatorics number theory

На доске написали 100 дробей, у которых в числителях стоят все числа от 1 до 100 по одному разу и в знаменателях стоят все числа от 1 до 100 по одному разу. Оказалось, что сумма этих дробей является несократимой дробью со знаменателем 2. Докажите, что можно поменять местами числители двух дробей так, чтобы сумма стала несократимой дробью с нечётным знаменателем.

Можно поменять местами числители двух дробей так, чтобы сумма стала несократимой дробью с нечётным знаменателем.

Пусть вначале в сумму входила дробь \( \frac{a}{2} \). Докажем, что в исходной сумме найдётся такая дробь \( \frac{b}{c} \) с нечётным знаменателем \( c \), что числа \( a \) и \( b \) имеют разную чётность. Действительно, дробей с нечётными знаменателями ровно 50, и число \( a \) не является числителем ни одной из них. Поэтому среди числителей таких дробей не больше 49 имеют ту же чётность, что и \( a \).

Поменяем теперь местами числители \( a \) и \( b \). Сделаем это в два приёма: сначала поменяем числитель у дроби со знаменателем 2 (сумма изменилась на нечётное число \( a - b \) половинок и, значит, превратилась в целое число), а затем — числитель дроби со знаменателем \( c \) (сумма изменилась на дробь с нечётным знаменателем, то есть стала дробью с нечётным знаменателем).

ARMO 2015, заключительный этап.
ID: 50 🏷 ARMO 📅 2015 🎓 10 ★★★★★★★☆☆☆ Сложно
combinatorics number theory fractions parity modular arithmetic

Пусть \( n > 1 \) – натуральное число. Выпишем дроби \( \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n} \) и приведём каждую к несократимому виду; сумму числителей полученных дробей обозначим через \( f(n) \). При каких натуральных \( n > 1 \) числа \( f(n) \) и \( f(2015n) \) имеют разную чётность?

При всех натуральных \( n > 1 \).

Пусть \( n = 2^t \cdot m \), где \( t \geq 0 \), а число \( m \) нечётно. Докажем, что число \( f(n) \) чётно ровно в двух случаях: либо \( n \) нечётно и \( m \equiv 1 \pmod{4} \), либо же \( n \) чётно и \( m \equiv 3 \pmod{4} \).

Первый способ. Рассмотрим произвольную дробь \( \frac{k}{n} \). Если \( k \) делится на \( 2^{t+1} \), то числитель этой дроби после сокращения будет чётен, в противном случае он будет нечётен. Среди чисел \( 1, 2, \ldots, n - 1 \) есть ровно \( \frac{m-1}{2} \) чисел, делящихся на \( 2^{t+1} \). Значит, в сумме \( f(n) \) имеется ровно \( n - 1 - \frac{m-1}{2} \) нечётных слагаемых. Поэтому \( f(n) \) чётно тогда и только тогда, когда числа \( n - 1 \) и \( \frac{m-1}{2} \) имеют одинаковую чётность, что и требовалось.

Второй способ. Пусть \( n \) нечётно (то есть \( t = 0 \)). Тогда числитель дроби \( \frac{k}{n} \) не меняет чётность после сокращения. Значит, количество нечётных числителей будет равно \( \frac{n-1}{2} \), и число \( f(n) \) чётно ровно тогда, когда чётно число \( \frac{n-1}{2} \), то есть при \( m \equiv 1 \pmod{4} \).

Пусть \( n \) чётно (\( t > 0 \)). Среди дробей со знаменателем \( n \) есть дробь, равная \( \frac{1}{2} \) и вносящая в \( f(n) \) слагаемое 1. Все остальные дроби разбиваются на пары вида \( \left(\frac{a}{n}, \frac{n-a}{n}\right) \). Поскольку сумма дробей в паре равна 1, после сокращения они переходят в пары несократимых дробей с одинаковым знаменателем вида \( \left(\frac{b}{d}, \frac{d-b}{d}\right) \). Вклад такой пары дробей в \( f(n) \) равен \( d \), и, если \( d \) чётно, он не влияет на чётность числа \( f(n) \).

Таким образом, чётность \( f(n) \) противоположна чётности аналогичной суммы для дробей, то есть чётности числа \( f(m) \) (при \( m = 1 \) она противоположна чётности \( f(1) = 0 \)). Отсюда и следует требуемое.

Осталось заметить, что числа \( n \) и \( 2015n \) имеют одну чётность; кроме того, при нечётном \( m \) числа \( m \) и \( 2015m \) дают разные остатки при делении на 4. Значит, числа \( f(n) \) и \( f(2015n) \) всегда имеют разную чётность.

ARMO 2011, региональный этап, 11.2
ID: 49 🏷 ARMO 📅 2011 🎓 11 ★★★★★★★☆☆☆ Сложно
number theory integers inequality parity

Даны 2011 ненулевых целых чисел. Известно, что сумма любого из них с произведением оставшихся 2010 чисел отрицательна. Докажите, что если произвольным образом разбить все данные числа на две группы и перемножить числа в группах, то сумма двух полученных произведений также будет отрицательной.

Сумма произведений отрицательна.

Предположим, что среди данных чисел чётное количество отрицательных. Тогда среди них есть положительное число \(a\), и произведение всех чисел, кроме \(a\), положительно. Это противоречит условию. Значит, среди данных чисел нечётное число отрицательных.

Пусть \(x_1, x_2, \ldots, x_k\) и \(y_1, y_2, \ldots, y_m\) – две группы, на которые разбиты данные числа \((k + m = 2011)\). Ровно одно из двух произведений \(x_1x_2\ldots x_k\) и \(y_1y_2\ldots y_m\) (а именно то, в котором нечётное число отрицательных сомножителей) – отрицательно; пусть \(x_1x_2\ldots x_k < 0\), \(y_1y_2\ldots y_m > 0\). Среди чисел \(x_1, x_2, \ldots, x_k\) найдётся отрицательное, скажем, \(x_1 < 0\). Тогда \(x_2\ldots x_k > 0\), а значит, \(x_2\ldots x_k \geq 1\) (так как числа целые). Следовательно,

\(x_1x_2\ldots x_k + y_1y_2\ldots y_m \leq x_1 + y_1y_2\ldots y_mx_2\ldots x_k < 0.\)