Страница:
<< 22 23 24 25
26 27 28 >> [Всего задач: 369]
|
|
|
Сложность: 4
Классы: 8,9,10
|
На доске написано 10 натуральных чисел. Докажите, что из этих чисел можно выбрать несколько чисел и расставить между ними знаки "+" и "–" так, чтобы полученная в результате алгебраическая сумма делилась на 1001.
Подсказка
Рассмотрите вначале только суммы со знаками "+". Затем покажите, что из одной из этих сумм можно вычесть другую так, чтобы результат делился на 1001.
Решение
Рассмотрим всевозможные суммы нескольких из выписанных чисел. Количество таких сумм будет равно 210 = 1024 (мы учитываем пустую сумму). Согласно принципу Дирихле некоторые две из этих сумм S1 и S2 дают одинаковый остаток при делении на 1001. Разность этих сумм S1 – S2 делится на 1001 и представляет собой сумму нескольких данных чисел со знаками "+" или "–".
|
|
|
Сложность: 4
Классы: 9,10,11
|
Докажите, что существуют числа, не менее чем 100 способами представимые в виде суммы 2001 слагаемого, каждое из которых является 2000-й степенью целого числа.
Подсказка
Рассмотрите всевозможные суммы из 2001 2000-х степеней первых
N чисел натурального ряда. Сколько будет таких сумм?
Решение
Рассмотрим числа 1, 2, 3, ...,
N. Из 2000-х степеней этих чисел будем составлять всевозможные суммы, в каждой из которых участвует 2001 слагаемое. Таких сумм (без учета порядка слагаемых) всего будет не меньше чем
N2001/
2001! (каждое слагаемое может быть выбрано
N способами, и в результате перестановки слагаемых одинаковыми оказываются не более 2001! сумм). С другой стороны, каждая из рассматриваемых сумм не больше чем 2001
N2000. Поэтому если
N2001/
2001! > 100·2001
N2000 (то есть
N > 100·2001·2001!, то не менее 100 сумм принимают одно и то же значение (что нам и требуется).
|
|
|
Сложность: 4
Классы: 8,9,10
|
Набор чисел A1, A2, ..., A100 получен некоторой перестановкой из чисел 1, 2, ..., 100. Образуют сто чисел:
B1 = A1, B2 = A1 + A2, B3 = A1 + A2 + A3, ..., B100 = A1 + A2 + A3 + ... + A100.
Докажите, что среди остатков от деления на 100 чисел B1, B2, ..., B100 найдутся 11 различных.
Решение
Пусть различных остатков не более десяти: r1, r2, ..., r10. Расcмотрим множество S, состоящее из всевозможных попарных разностей ri – rj (i ≠ j) и нуля. Количество элементов множества S не превышает 91. С другой стороны, для всех k (2 ≤ k ≤ 100) Ak = Bk – Bk–1 ≡ s (mod 100) для некоторого s 
S, то есть S содержит числа, сравнимые по модулю 100 со всеми числами от 1 до 100 за исключением, возможно, A1. Таким образом, S содержит не менее 99 чисел. Противоречие.
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
Даны таблица 100×100 клеток и N фишек. Рассматриваются все такие расстановки фишек в клетки таблицы, что никакие две фишки не стоят в соседних клетках. При каком наибольшем N в каждой из этих расстановок можно найти хотя бы одну фишку, от перемещения которой в соседнюю клетку заданное условие не нарушится? (Соседними считаются клетки, имеющие общую сторону.)
Решение
Назовём расстановку фишек жёсткой, если перемещение любой фишки в соседнюю клетку нарушает требуемое условие. Жёсткая расстановка из ста фишек существует: поставим все фишки на клетки большой диагонали.
То, что любая расстановка 99 (или менее) фишек нежёсткая, фактически доказано в задаче 35395.
Ответ
При N = 99.
|
|
|
Сложность: 4
Классы: 8,9,10,11
|
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Решение
Докажем утверждение индукцией по числу n жителей города. База (n ≤ 2) очевидна.
Шаг индукции. Пусть n ≥ 3, а m – общее количество звонков в этот день. По условию m ≤ n, поэтому найдётся житель A, разговаривавший не более чем с двумя жителями (в противном случае m ≥ 3n/2 > n). По предположению индукции, всех жителей города, кроме A, можно разбить на три группы так, чтобы выполнялось условие задачи. Житель A не разговаривал с жителями, входящими в одну из групп, поэтому его можно добавить к этой группе, сохранив в силе требуемое утверждение.
Страница:
<< 22 23 24 25
26 27 28 >> [Всего задач: 369]
Фильтр
