19. Задачи олимпиадного уровня
Чтобы получить дополнительный функционал нужно войти.
(ЕГЭ,2017) Каждый из 28 студентов или писал одну из двух контрольных работ, или писал обе контрольные работы. За каждую работу можно было получить целое число баллов от 0 до 20 включительно. По каждой из двух контрольных работ в отдельности средний балл составил 15. Затем каждый студент назвал наивысший из своих баллов (если студент писал одну работу, то он назвал балл за неё). Среднее арифметическое названных баллов оказалось равно \(S\).
a) Приведите пример, когда \(S<15\).
б) Могло ли значение \(S\) быть равным 5 ?
в) Какое наименьшее значение могло принимать \(S\), если обе контрольные работы писали 10 студентов?
Решение
а) например, если 20 студентов писали обе контрольные работы и получили по 18 баллов, по 4 студента писали только одну из двух контрольных работ и получили по 0 баллов
Ответ
(ЕГЭ,2017) С натуральным числом проводят следующую операцию: между каждыми двумя его соседними цифрами записывают сумму этих цифр (например, из числа 1923 получается число 110911253 ).
a) Приведите пример числа, из которого получается 2108124117.
б) Может ли из какого-нибудь числа получиться число 37494128 ?
в) Какое наибольшее число, кратное 11 , может получиться из трёхзначного числа?
Ответ
(ЕГЭ,2017) В каждой клетке квадратной таблицы \(6 \times 6\) стоит натуральное число, меньшее 7. Вася в каждом столбце находит наименьшее число и складывает шесть найденных чисел. Петя в каждой строке находит наименьшее число и складывает шесть найденных чисел.
a) Может ли сумма у Пети получиться в два раза больше, чем сумма у Васи?
б) Может ли сумма у Пети получиться в шесть раз больше, чем сумма у Васи?
в) В какое наибольшее число раз сумма у Пети может быть больше, чем сумма у Васи?
Ответ
(ЕГЭ,2016) Множество чисел назовём хорошим, если его можно разбить на два подмножества с одинаковой суммой чисел.
а) Является ли множество \(\{200 ; 201 ; 202 ; \ldots ; 299\}\) хорошим?
б) Является ли множество \(\left\{2 ; 4 ; 8 ; \ldots ; 2^{100}\right\}\) хорошим?
в) Сколько хороших четырёхэлементных подмножеств у множества \(\{1 ; 2 ; 4 ; 5 ; 7 ; 9 ; 11\} ?\)
Решение
a) Разобьём множество \(\{200 ; 201 ; 202 ; \ldots ; 299\}\) на 50 пар, сумма чисел в каждой из которых равна 499: \(\{200 ; 299\},\{201 ; 298\}, \ldots\)
Множество \(\{200 ; 201 ; 202 ; \ldots ; 299\}\) можно разбить на два подмножества, в каждом из которых по 25 таких пар. Значит, сумма чисел в этих двух подмножествах одинакова и множество \(\{200 ; 201 ; 202 ; \ldots ; 299\}\) является хорошим.
б) Заметим, что \(2^{100}>2^{100}-1=2^{99}+2^{98}+\ldots+4+2+1\). Поэтому сумма чисел в подмножестве множества \(\left\{2 ; 4 ; 8 ; \ldots ; 2^{100}\right\}\), содержащем \(2^{100}\), всегда больше суммы остальных чисел, следовательно, множество \(\left\{2 ; 4 ; 8 ; \ldots ; 2^{100}\right\}\) не является хорошим.
в) Заметим, что четырёхэлементное множество является хорошим в двух случаях: либо одно число является суммой трёх других, либо множество содержит две пары чисел с равными суммами.
Подмножества множества \(\{1 ; 2 ; 4 ; 5 ; 7 ; 9 ; 11\}\), удовлетворяющие первому случаю, - это \(\{1 ; 2 ; 4 ; 7\},\{2 ; 4 ; 5 ; 11\}\).
Рассмотрим второй случай. Заметим, что числа 2 и 4 либо одновременно входят в хорошее четырёхэлементное подмножество, либо одновременно не входят в него, поскольку сумма всех чисел хорошего подмножества чётна. Если 2 и 4 входят в подмножество, то либо сумма двух других чисел равна 6 - это единственное подмножество \(\{1 ; 2 ; 4 ; 5\}\), либо разность двух других чисел равна 2. Получаем хорошие подмножества:
\begin{equation*}
\{1 ; 2 ; 4 ; 5\},\{2 ; 4 ; 5 ; 7\},\{2 ; 4 ; 7 ; 9\},\{2 ; 4 ; 9 ; 11\} .
\end{equation*}
Если 2 и 4 не входят в подмножество, то хорошее подмножество лежит в множестве \(\{1 ; 5 ; 7 ; 9 ; 11\}\). Получаем хорошие подмножества:
\begin{equation*}
\{1 ; 5 ; 7 ; 11\},\{5 ; 7 ; 9 ; 11\} .
\end{equation*}
Всего получилось 8 хороших подмножеств.
Ответ
(ЕГЭ,2016) На доске написаны числа 2 и 3. За один ход два числа \(a\) и \(b\), записанные на доске, заменяются на два числа: или \(a+b\) и \(2 a-1\), или \(a+b\) и \(2 b-1\) (например, из чисел 2 и 3 можно получить либо 3 и 5 , либо 5 и 5).
a) Приведите пример последовательности ходов, после которых одно из двух чисел, написанных на доске, окажется числом 13.
б) Может ли после 200 ходов одно из двух чисел, написанных на доске, оказаться числом 400 ?
в) Сделали 513 ходов, причём на доске никогда не было написано одновременно двух равных чисел. Какое наименьшее значение может принимать разность большего и меньшего из полученных чисел?
Решение
a) Число 13 могло получиться в результате следующей последовательности ходов:
\begin{equation*}
(2 ; 3) ;(3 ; 5) ;(5 ; 8) ;(9 ; 13)
\end{equation*}
б) После первого хода на доске будет записано либо 3 и 5 , либо 5 и 5 . Заметим, что после каждого последующего хода каждое из двух чисел увеличивается хотя бы на 2. Значит, после 200 ходов меньшее из двух чисел будет не меньше \(3+199 \cdot 2=401\). Значит, после 200 ходов на доске не может оказаться число 400 .
в) Пусть в какой-то момент на доске была написана пара чисел \(a\) и \(b\), причём \(b>a\). Тогда после хода на доске будет написано либо \(2 a-1\) и \(a+b\), либо \(a+b\) и \(2 b-1\). В первом из этих случаев разность чисел равна \(b-a+1\), а во втором \(b-a-1\). То есть после каждого хода разность большего и меньшего чисел изменяется на 1 , причём для любых двух различных чисел можно сделать ход так, чтобы разность увеличилась, и так, чтобы разность уменьшилась.
Изначально разность большего и меньшего чисел была равна 1 , а после каждого хода её чётность меняется. Значит, после 513 ходов разность должна быть чётной. Поэтому наименьшая возможная разность - это 2.
Например, если сначала сделать 257 ходов, увеличивающих разность, а затем 256 ходов, уменьшающих разность, то получится два числа, разность которых равна 2 .
Ответ
(ЕГЭ,2016) На доске написаны числа \(1,2,3, \ldots, 30\). За один ход разрешается стереть произвольные три числа, сумма которых меньше 35 и отлична от каждой из сумм троек чисел, стёртых на предыдущих ходах.
a) Приведите пример последовательных 5 ходов.
б) Можно ли сделать 10 ходов?
в) Какое наибольшее число ходов можно сделать?
Решение
a) Пример последовательных 5 ходов (стёрты тройки чисел):
\begin{equation*}
\begin{gathered}
(1 ; 6 ; 11) ;(2 ; 7 ; 12) ;(3 ; 8 ; 13) ; \\
(4 ; 9 ; 14) ;(5 ; 10 ; 15) .
\end{gathered}
\end{equation*}
б) Пусть сделано 10 ходов, то есть стёрли все числа. С одной стороны, сумма чисел \(1,2, \ldots, 30\) равна \(\frac{1+30}{2} \cdot 30=465\). С другой стороны, каждая из сумм стираемых трёх чисел меньше 35 , значит, сумма всех стёртых за 10 ходов чисел меньше 350 . Противоречие. Значит, нельзя сделать 10 ходов.
в) Пусть можно сделать 7 ходов. Тогда сумма стёртых за 7 ходов чисел не меньше
\begin{equation*}
1+2+3+\ldots+20+21=231 \text {. }
\end{equation*}
С другой стороны, эта сумма не больше суммы семи различных натуральных чисел, меньших 35 , то есть не больше
\begin{equation*}
34+33+32+31+30+29+28=217 .
\end{equation*}
Значит, невозможно сделать 7 ходов.
Пример последовательных 6 ходов (стёрты тройки чисел):
\begin{equation*}
\begin{gathered}
(21 ; 12 ; 1) ;(20 ; 11 ; 2) ;(19 ; 10 ; 3) \\
(18 ; 9 ; 4) ;(17 ; 8 ; 5) ;(16 ; 7 ; 6)
\end{gathered}
\end{equation*}