Страница: << 35 36 37 38 39 40 41 >> [Всего задач: 393]      

В Камелот съехались $100$ рыцарей Круглого Стола, любые два из которых либо дружат, либо враждуют (дружба и вражда взаимны). Фея Моргана может выбрать любого рыцаря и сделать так, что он поссорится со всеми своими друзьями и при этом подружится со всеми своими врагами. Накладывать это заклинание Моргана может сколько угодно раз. Докажите, что она сможет добиться того, чтобы в итоге образовались такие две группы по $5$ рыцарей, что каждый рыцарь из первой пятёрки будет враждовать с каждым рыцарем из второй.

Прислать комментарий

Решение

На микросхеме $2025$ различных элементов, некоторые пары из которых соединены проводами. Жора хочет раскидать элементы по $n$ платам так, чтобы никакие два элемента одной платы не были соединены проводами. Жора посчитал, что если плат будет всего две, то у него будет $2$ способа, а если плат $2025$ – то $2025~\cdot~2024^{2024}$ способов. Сколько проводов на микросхеме?

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

Прислать комментарий

Решение

Назовём ходы коня, при которых он смещается на две клетки по горизонтали и на одну по вертикали, горизонтальными, а остальные — вертикальными. Требуется поставить коня на одну из клеток доски $46\times46$, после чего чередовать им горизонтальные и вертикальные ходы. Докажите, что если запрещено посещать клетки более одного раза, то будет сделано не более 2024 ходов.

Прислать комментарий

Решение

На клетчатой доске $2n\times 2n$ расставлены $2n$ ладей ($n$ — натуральное число). Докажите, что можно выбрать либо $n$ горизонталей, либо $n$ вертикалей и снять все ладьи с выбранных $n$ рядов так, что оставшиеся ладьи не будут бить друг друга.

Прислать комментарий

Решение

Между некоторыми из 2n городов установлено воздушное сообщение, причём каждый город связан (беспосадочными рейсами) не менее чем с n другими.
  а) Докажите, что если отменить любые  n – 1  рейсов, то всё равно из любого города можно добраться в любой другой на самолётах (с пересадками).
  б) Укажите все случаи, когда связность нарушается при отмене n рейсов.

Прислать комментарий

Решение

Страница: << 35 36 37 38 39 40 41 >> [Всего задач: 393]