Олимпиадные задачи по теме «Комбинаторика (прочее)» для 11 класса - сложность 4-5 с решениями

По рёбрам треугольной пирамиды ползают четыре жука, при этом каждый жук всё время остаётся только в одной грани (в каждой грани – свой жук). Каждый жук обходит границу своей грани в определённом направлении, причём так, что каждые два жука по общему для них ребру ползут в противоположных направлениях. Докажите, что если скорости (возможно, непостоянные) каждого из жуков всегда больше 1 см/с, то когда-нибудь какие-то два жука обязательно встретятся.

Продавец хочет разрезать кусок сыра на части, которые можно будет разложить на две кучки равного веса. Он умеет разрезать любой кусок сыра в одном и том же отношении  <i>a</i> : (1 – <i>a</i>)  по весу, где  0 < <i>a</i> < 1.  Верно ли, что на любом промежутке длины 0,001 из интервала  (0, 1)  найдётся значение <i>a</i>, при котором он сможет добиться желаемого результата с помощью конечного числа разрезов?

<i>k</i> вершин правильного <i>n</i>-угольника закрашены. Закраска называется <i>почти равномерной</i>, если для любого натурального <i>m</i> верно следующее условие: если <i>M</i>₁ – множество <i>m</i> расположенных подряд вершин и <i>M</i>₂ – другое такое множество, то количество закрашенных вершин в <i>M</i>₁ отличается от количества закрашенных вершин в <i>M</i>₂ не больше чем на 1. Доказать, что для любых натуральных <i>n</i> и  <i>k</i> ≤ <i>n</i>  почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множест...

<i>N</i> друзей одновременно узнали <i>N</i> новостей, причём каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями.

Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.

Какое минимальное количество часов необходимо, чтобы все узнали все новости? Рассмотрите три случая:

  а)  <i>N</i> = 64,

  б)  <i>N</i> = 55,

  в)  <i>N</i> = 100.

В ящике лежат два ящика поменьше, в каждом из них ещё по два ящика и т.д. <i>n</i> раз. В каждом из 2^<i>n</i> маленьких ящиков лежит по монете, причём одни вверх гербом, а остальные – вверх решкой. За один ход разрешается перевернуть один любой ящик вместе со всем, что в нём лежит. Доказать, что не больше, чем за <i>n</i> ходов можно расположить ящики так, что число монет, лежащих вверх гербом, будет равно числу монет, лежащих вверх решкой.

Около таверны стоят $100$ эльфов, $100$ гномов и $100$ орков. Сначала в неё заходят $10$ эльфов, $10$ гномов и $10$ орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома – орк, а после выхода орка – эльф. Могло ли оказаться так, что в какой-то момент в таверне побывали все возможные компании из $30$ существ ровно по одному разу? Все $300$ существ различны.

Белая фигура «жук» стоит в угловой клетке доски $1000\times n$, где $n$ — нечётное натуральное число, большее $2020$. В двух ближайших к ней углах доски стоят два чёрных шахматных слона. При каждом ходе жук или переходит на клетку, соседнюю по стороне, или ходит как шахматный конь. Жук хочет достичь противоположного угла доски, не проходя через клетки, занятые или атакованные слоном, и побывав на каждой из остальных клеток ровно по одному разу. Покажите, что количество путей, по которым может пройти жук, не зависит от $n$.