Тема КОМБИНАТОРИКА

Логика → .05 Много объектов и большие числа

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Логика

Строим пример

Невозможность определить гарантированно

Эффект +- 1

Учти лишнее

Много объектов и большие числа

Истинные и ложные высказывания

Утверждение о существование и построение отрицания к ним

Рассуждения от противного

Рыцари и лжецы

Мудрецы и фокусы

Принцип Дирихле

Оценка + пример

Круги Эйлера

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#68025

На доске написаны 100 различных натуральных чисел. Петя записал на доску красным цветом все их попарные суммы, а синим цветом — все их попарные произведения. Может ли оказаться так, что для каждого красного числа найдётся делящееся на него синее? (Допускается, что одно и то же синее число может делиться на разные красные числа).

Источники: Курчатов-2023, 11.1 (см. olimpiadakurchatov.ru)

Показать ответ и решение

Пусть на доске записаны числа $200!⋅1,200!⋅2,200!⋅3,...,200!⋅100.$ Сумма любой пары имеет вид $200!⋅x, где 2≤ x≤ 199.$ А произведение - $2 (200!) ⋅y,$ где $y ∈ ℕ.$ Так как $200!$ делится на все возможные значения $x,$ то в выбранной паре произведение чисел делится на их же сумму.

Ответ: да

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#35711

На крайней клетке доски $1×99$ сидит кузнечик. Одним прыжком он может перепрыгнуть через одну или две клетки и приземлиться в следующей. Сможет ли он побывать на всех клетках ровно по одному разу?

Показать ответ и решение

Заметим, что кузнечик может перемещаться на 5 клеток вперед, посетив только все предыдущие (как это сделать показано на картинке ниже). То есть мы можем уменьшать длину полосы на 5. Тогда уменьшим ее до 9. Дальше будем действовать как рисунке ниже.

Ответ: Cможет

Ошибка.
Попробуйте повторить позже

Задача 3#35712

Назовем натуральное число зеброй, если в его записи строго чередуются чётные и нечётные цифры. Может ли разность двух 100-значных зебр быть 100-значной зеброй?

Показать ответ и решение

Например,

50...50− 25...25 =25...25

Ответ: Может

Ошибка.
Попробуйте повторить позже

Задача 4#35713

1) Можно ли прямоугольник $10× 20$ разрезать по границам клеток на 19 различных прямоугольников? 2) А на 20?

Показать ответ и решение

Оба примера на картинке ниже.

Ответ: Можно

Ошибка.
Попробуйте повторить позже

Задача 5#35714

Есть 30 яблок, одно из них — явно червивое. Петя и Вася едят по очереди от одного до трёх яблок за раз. Тот, кому достанется червивое, — проиграл. Петя начинает. Кто из них может выиграть, как бы ни играл соперник?

Показать ответ и решение

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

Ответ: Петя

Ошибка.
Попробуйте повторить позже

Задача 6#35715

На шахматную доску $8× 8$ по одной выставляются ладьи так, чтобы каждая выставленная ладья побила (на момент выставления) чётное число пустых полей. Считается, что ладья не бьёт клетку, на которой стоит. Какое наибольшее число ладей можно выставить?

Показать ответ и решение

Выставляем ладей на главную чёрную диагональ, потом на параллельные ей соседние белые диагонали, потом на параллельные соседние с предыдущими белые диагонали, и т. д. В конце выставляются ладьи на чёрные поля в произвольном порядке.

Ответ: 64

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#35716

Расставьте 48 ладей на клетчатой доске $10×10$ так, чтобы каждая била 2 или 4 пустые клетки.

Показать ответ и решение

Как на картинке.

Ответ: Можно

Ошибка.
Попробуйте повторить позже

Задача 8#35717

На конференции было три секции: химики, алхимики и лекари. По кругу выстроились 112 участников, среди которых химиков и лекарей поровну. На вопрос «Верно ли, что оба твоих соседа из одной секции» каждый ответил «Да». Химик всегда говорит правду, алхимик всегда лжёт, а лекарь лжет, если стоит рядом с алхимиком (а иначе говорит правду). Могло ли в этом круге быть 66 алхимиков?

Показать ответ и решение

Например, круг состоит из семи десятков вида ААXААХААЛЛ, затем три группы по 14 человек вида ААXААХААХААЛЛЛ.

Ответ: Могло

Ошибка.
Попробуйте повторить позже

Задача 9#71911

У барона Мюнхгаузена есть набор гирь $1000$ различных целых весов, по $21000$ гирь каждого веса. Барон утверждает, что если взять по одной гире каждого веса, то общий вес этих $1000$ гирь будет меньше $1010 2 ,$ причём этот вес невозможно набрать гирями из этого набора другим способом. Могут ли слова барона оказаться правдой?

Источники: СпбОШ - 2019, задача 11.5(см. www.pdmi.ras.ru)

Показать ответ и решение

Пусть $k =1000.$ Докажем, что подойдет набор гирь с весами

k k−1 k k−2 k 0 ak−1 =2 − 2 ,ak−2 = 2 − 2 ,...,a0 = 2 − 2 .

Если взять по одной гире каждого веса, сумма весов равна

k k−1 1 0 k 2010 s =k ⋅2 − 2 − ⋅⋅⋅− 2 − 2 = (k − 1)⋅2 +1 <2 .

Заметим, что

s≡ 1 (mod 2k),a≡ −2i (mod 2k) i

Тогда любой способ набрать этими гирями суммарный вес $s$ повзоляет представить число $s,$ дающее остаток $1$ по модулю $2k,$ как сумму нескольких слагаемых с остатком $− 2i.$ Следовательно, можно набрать некторое число $t,$ сравнимое с $2k− 1$ по модулю $2k,$ как сумму нескольких слагаемых вида $2i.$

Будем в такой сумме заменять две одинаковые степени двойки на одну более крупную, пока это возможно. В результате получится, что $2k− 1,$ набрано как сумма различных степеней двойки. Но это можно сделать единственным способом: сложив все меньшие степени двойки, этот соответствует сумме

a + a +⋅⋅⋅+ a k−1 k−2 0

Остается лишь добавить, что замена одной степени двойки на две меньших (обратная приведённым операциям) дает замену $ai$ на $2ai− 1,$ что увеличивает сумму. Значит, наш способ единственен.

Ответ: да

Предыдущая подтема

Следующая подтема