Графы и турниры

Вместо того, чтобы решать новую задачу, мы переведем ее на язык старой. Будем выписывать строку из букв З и С. Пишем З, если на очередном шаге добавили золотую монету, и С, если убрали серебряную.

Посмотрим, как полученный ряд связан с выписываемыми числами. Если мы встречаем в ряду З, то выписанное на этом шаге число равно количеству С, правее этой буквы З. Наоборот, если мы встретили С, то выписанное на этом шаге число равно количеству З, левее этой буквы С. Таким образом, мы получили в точности предыдущую задачу, которую уже решили.

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

Если мы берем камень из кучи, в которой было камней, и добавляем в кучу, где было камней, то добавляется ребер, а вычитается ребро. Таким образом, количество ребер изменяется на Но это как раз равно заработку Сизифа. Поэтому изменение количества ребер во вспомогательном графе равно заработку Сизифа. Так как по условию повторилась ситуация, в которой в каждой куче содержится то же число камней, что и изначально, то количество ребер во вспомогательном графе после всех проведенных операций не изменилось. Значит, заработок Сизифа равен

Пусть в турнире участвовали девочек и мальчиков. Тогда девочки в партиях между собой набрали очков, а мальчики Разница составляет очков. По условию мальчики и девочки в сумме набрали поровну. Значит, девочки набрали больше на очков в партиях между мальчиками и девочками. В этих партиях было всего разыграно очков, поэтому , то есть Но натуральное число, и потому и неравенство обращается в равенство. Значит, в турнире участвовала одна девочка и три мальчика. Девочка набрала не менее очков, следовательно, она выиграла у всех мальчиков и заняла первое место.

Будем называть вершины игроками. Выберем каких-нибудь двух игроков. Один из них выиграл у другого. Выигравшего обозначим A, а проигравшего Б и образуем цепочку из двух игроков, где А стоит перед Б. Пусть В — какой-то третий игрок. Если он выиграл у А, поставим его в начало цепочки. Если он проиграл A, но выиграл у Б, поставим В между A и Б. Если В проиграл обоим, поставим его после Б.

Дальше действуем аналогично: пусть сколько-то игроков уже составляют цепочку с нужным свойством, и пусть игрок И не принадлежит цепочке. Если он выиграл у первого в цепочке, добавим И в начало цепочки. Если нет, найдём последнего игрока в цепочке, который выиграл у И, и поставим И после него. Тогда цепочка по-прежнему будет обладать нужным свойством. Продолжая так, мы включим в цепочку всех игроков.

Пусть шахматист выиграл партий, свел вничью партий и проиграл партий. Тогда он набрал очков. Кроме того, так как он сыграл партий, то . Умножим первое равенство на и вычтем из него второе. После сокращения получим , то есть побед на 5 больше, чем поражений.

В одну сторону лемма очевидна. Докажем, что если для любого набора из юношей количество знакомых им в совокупности девушек не меньше то каждого из них можно поженить на знакомых девушках. Создадим для каждого юноши его клон, не считая его самого. Нетрудно убедиться, что для полученного графа выполняется условие леммы Холла. Следовательно, в полученном графе есть паросочетание, покрывающее юношей. Тогда можно каждого юношу поженить на жёнах его клонов и получить требуемое.

Связный граф эйлеров, если в нём 0 или 2 вершины нечетной степени. В противном случае, граф будет неэйлеровым.

В полном графе из вершин степень каждой вершины равна . То есть, если - чётно, то - нечётно, и в случае получается, что у нас вершин нечётной степени, и тогда граф неэйлеров.

Если же , то получаем отрезок между двумя точками, который, очевидно, эйлеров.

А если и, наоборот, - нечётно, то - чётно, и поэтому у нас все вершины чётной степени, значит, такой граф эйлеров (очевидно, он связен).