Всего: 513 1–20 | 21–40 | 41–60 | 61–80 | 81–100 | 101–120 | 121–140 …
Добавить в вариант
где xi — число в вершине, di — её глубина в подвешенном дереве. Легко видеть, что каждая миграция не из корня дерева отдаёт единичку наверх и менее n на уровень вниз, то есть сумма строго увеличивается. Но всех возможных сумм конечное число, так что рано или поздно будет возможна миграция только из корня, а это значит, что там 
N олигархов построили себе страну c N городами, каждый олигарх владеет ровно одним городом. Кроме того, каждый олигарх построил несколько дорог между городами: любая пара городов соединена максимум одной дорогой каждого из олигархов (между двумя городами может быть несколько дорог, принадлежащих разным олигархам). Суммарно было построено d дорог. Некоторые олигархи хотели бы создать корпорацию, объединив свои города и дороги, так чтобы при этом из любого города корпорации можно было доехать до любого другого ее города по дорогам этой корпорации, возможно, заезжая по дороге в города других олигархов. Но оказалось, что никакая группа, в которой меньше N олигархов, создать корпорацию не может! При каком наибольшем d это возможно?
сопоставлена дороге ij, принадлежащей олигарху k, т. е. всего 
дорог. 
У Андрюши есть 100 камней разного веса, причем он различает камни по внешнему виду, но не знает, сколько именно весит каждый камень и как они упорядочены по весу. Андрюша может вечером положить на стол ровно 10 камней, а ночью домовой разложит их по возрастанию веса. Но если в доме живёт ещё и барабашка, то под утро он обязательно поменяет какие-то два из разложенных камней местами. Всё это известно Андрюше, но он не знает, есть ли в доме барабашка. Сможет ли он это узнать?
В экзамене 25 тем, по каждой из которых заготовлено 8 вопросов. В билет входят 4 вопроса по разным темам. Можно ли заготовить 50 билетов так, чтобы каждый вопрос встречался в них ровно один раз и для любых двух тем был билет, в котором есть вопросы по ним обеим?
по модулю 5. Каждый билет будем пони- мать как четвёрку тем, тогда требуется предъявить 50 четвёрок так, что каждая тема находится ровно в 8 четвёрках и каждая пара тем — ровно в одной четвёрке. Работая с парами остатков по модулю 5, мы можем складывать (покоординатно по модулю 5). Рассмотрим 25 сдвигов четвёрки 
содержится ровно в 8 четвёрках, поскольку она единственным образом представима в каждом из видов (*) или (**). Докажем, что любые две различные темы 
содержатся вместе ровно в одной четвёрке. Для этого надо установить, что их разность 
представима единственным образом либо как разность двух тем из A, либо как разность двух тем из 
Несложно про- верить, что эти 24 разности — 12 разностей для A и 12 разностей для 
—
есть хотя бы две отмеченные клетки. Поскольку из доски 
можно вырезать 25 таких квадратов, в ней должно быть не менее 50 отмеченных клеток. Пример с 50 отмеченными клетками получается, если отметить клетки, первая координата которых четна.
— не менее двух. Поскольку из доски 
можно вырезать 16 квадратов 
всего должно быть от мечено по крайней мере 
клеток. Пример с 56 от меченными клетками показан н а рисунке.
есть хотя бы две от меченные клетки. Поскольку доска 
разрезается на 24 таких прямоугольника, в ней должно быть не менее 48 от меченных клеток. Пример с 48 отмеченными клетками получается, если отметить клетки, сумма координат которых делится на 4.На трибунах хоккейной арены несколько рядов по 168 мест в каждом ряду. На финальный матч в качестве зрителей пригласили 2016 учеников нескольких спортивных школ, не более 40 от каждой школы. Учеников любой школы требуется разместить на одном ряду. Какое наименьшее количество рядов должно быть на арене, чтобы это в любом случае удалось сделать?
то 
и 
но тогда 
что невозможно. Таким образом, в каждой десятке не более четырех выбранных чисел, а в первой тысяче чисел их не более 400, поскольку в тысяче сто десяток.
а королей — не более 56. Расстановка 56 королей показана на рисунке.На встрече любителей кактусов 80 кактусофилов представили свои коллекции, каждая из которых состоит из кактусов разных видов. Оказалось, что ни один вид кактусов не встречается во всех коллекциях сразу, но у любых 15 человек есть кактусы одного и того же вида. Какое наименьшее общее количество видов кактусов может быть во всех коллекциях?
кактусов. Занумеруем кактусы числами от 1 до k. Для кактуса с номером i найдется кактусофил Ai, у которого его нет. Но тогда для кактусофилов A1, Клетки доски 2015 × 2015 раскрашены в шахматном порядке так, что угловые клетки черные. На одну из черных клеток поставлена фишка, а некоторая другая черная клетка отмечена. За ход разрешается переместить фишку на соседнюю клетку. Всегда ли можно обойти фишкой все клетки доски, побывав на каждой из них ровно по одному разу, и закончить обход в отмеченной клетке? (Две клетки являются соседними, если имеют общую сторону.)
найдется путь фишки, начинающийся в A, проходящий по всем клеткам доски и заканчивающийся в B.
Возможны два размещения черных клеток A и B: в соседних угловых клетках и в противоположных угловых клетках. С точностью до поворота доски они разобраны на верхних двух рисунках.
ни один из углов которой не совпадает с углом доски 
то подправим путь фишки из A в B, обходящий доску 
Перенаправим ее из d в f, затем по часовой стрелке по каемке доски до g и потом в c.
Пусть для определенности это клетка A (в противном случае A и B можно поменять ролями, рассмотрев обратный путь). Если клетка B расположена не на краю, то сделаем обход таким образом. От клетки A пойдем по каемке против часовой стрелки до клетки c, затем на клетку A′ и после этого по маршруту от A′ до B, который существует по предположению индукции (рис. б).
соседних островов; отправим их обратно на свои острова. Если есть колония с оставшегося соседнего острова, тоже отправим её обратно, если есть своя колония, отправим её на любой из соседних островов.1.4 Произошло некоторое число миграций. После этого на каждый остров высадилось по орнитологу. Каждый орнитолог может перелететь на другой остров на личном вертолёте по тем же воздушным коридорам. Однако в целях безопасности в течение суток запрещено взлетать с соседних островов и пролетать дважды по одному и тому же коридору или над одним и тем же островом. Докажите, тем не менее, что некоторые орнитологи могут за сутки переместиться на другие острова, чтобы на каждом острове орнитологов и колоний тупиков оказалось поровну.
Развернуть
1.4 Пусть изначально на каждом острове обитает одна колония, и пусть один из островов имеет d соседних. Чему может равняться максимально возможное количество колоний, способных поселиться на этом острове?
Развернуть
колония. Подвесим дерево за эту вершину как за корень и будем доказывать, что в каждой вершине, из которой вниз идет e рёбер, можно собрать 
колонию, проводя только миграции в её поддереве. Докажем это «индукцией от нижних вершин к верхним». Для листьев утверждение очевидно (в них и так есть одна колония), а в для любой другой вершины достаточно собрать нужное количество колоний в её непосредственных потомках, после чего проделать по одной миграции для каждого из них.
2.1 Докажите, что если в стране любые две школы соединяет ровно одна цепочка беспосадочных маршрутов, то эта страна гармонична.
Развернуть
а вершины на пути из y в z, как 
Тогда 
при 
(при 
по максимальности, а при 
можно было бы найти цикл). Осталось заметить, что последовательность 
—
2.2 Докажите, что если страна является гармоничной, то можно назвать некоторые школы добрыми, а остальные злодейскими так, чтобы любой беспосадочный маршрут соединял добрую школу со злодейской.
Развернуть
2.3 В стране Гиперляндии 2n школ, названиями которых являются все возможные последовательности из символов 0 и 1 длины n, при этом между школами есть беспосадочный маршрут тогда и только тогда, когда их названия отличаются ровно в одном символе. Докажите, что Гиперляндия — гармоничная страна.
Развернуть
