Рассмотрим связный граф на 2019 вершинах, в котором вершины представляют собой деревья, а ребра - тропинки между ними.
Назовем граф правильным, если из каждой вершины можно добраться до каждой.
У этого графа есть важное свойство: если удалить любое из ребер, граф не потеряет связность.
Из этого следует, что между любыми двумя вершинами существует по крайней мере два пути по ребрам (*).
Рассмотрим следующую тактику для волка: пусть лиса сделала ход. Рассмотрим две вершины, между которыми она установила одностороннее движение (пусть это вершины A и B). По (*) ясно, что между A и B, помимо самого ребра, соединяющего эти вершины, есть по крайней мере еще один путь. Рассмотрим любой из таких путей. Тактика волка будет заключаться в том, чтобы на любом из ребер, которое принадлежит пути, поставить противоположное направление по отношению к AB. Покажем, что такая тактика является для волка непроигрышной. То есть докажем, что после хода волка граф останется правильным. Предположим противное. Пусть из некоторой вершины X нельзя добраться до вершины Y. Рассмотрим два случая:
1) между X и Y есть ребро.
Тогда оно ориентировано. Поскольку волк следует тактике, то волк только что поставил одностороннее движение на XY. Но XY, согласно тактике, является частью пути между какими-то вершинами (пусть M и N). M и N друг для друга достижимы, точно так же M достижимо для X, а N для Y (без ограничения общности). Пусть из X можно добраться в Y (по ребру между ними), тогда добравшись из Y в N, а там из N в M, а из M в X мы доберемся из Y в X, тогда X и Y взаимно достижимы, противоречие.
2) между X и Y нет ребра.
Точно так же, XY - часть какого-то пути между двумя вершинами. Путь между XY состоит из взаимно достижимых вершин, соединенных ребрами ( доказано в 1) ). Значит, и X и Y взаимно достижимы, противоречие.
Итак, данная тактика является непроигрышной. Пусть волк не будет действовать по этой тактике. Тогда по этой тактике будет действовать лиса, а, значит, волк будет действовать по невыигрышной тактике (что называется неправильная игра). Пусть тогда волк будет действовать волк. Но тогда точно так же придется поступить и лисе. Осталось доказать, что лиса не может проиграть первым ходом. Пусть она изменила напр. на каких-то двух вершинах (они соединены ребром). Тогда они взаимно достижимы по второму пути (после хода лисы всего одно ребро ориентировано). Итак, при правильной игре будет ничья.
1) нацепление двоичного логарифма на все 3 куска неравенства
2) преобразование логарифма произведения в сумму логарифмов в левой и правой части, с последующим вычитанием логарифма от 5^к из всех 3 частей
3) подведение всех 3 частей к степени двойки
получаем такое неравенство:
а < 2^(s-k*log_2(5)) < a+1
Теперь сильное утверждение: любое число можно приблизить сколь угодно сильно, используя лишь s-k*log_2(5), увеличивая s и k до нужного порядка.
Тогда мы всегда можем найти такие k и s, что б двойка в оной степени подходила под наше неравенство, ибо мы можем приблизить любую действительную степень, значит и любое число после возведения двойки в эту степень.
Рассмотрим связный граф на 2019 вершинах, в котором вершины представляют собой деревья, а ребра - тропинки между ними.
Назовем граф правильным, если из каждой вершины можно добраться до каждой.
У этого графа есть важное свойство: если удалить любое из ребер, граф не потеряет связность.
Из этого следует, что между любыми двумя вершинами существует по крайней мере два пути по ребрам (*).
Рассмотрим следующую тактику для волка: пусть лиса сделала ход. Рассмотрим две вершины, между которыми она установила одностороннее движение (пусть это вершины A и B). По (*) ясно, что между A и B, помимо самого ребра, соединяющего эти вершины, есть по крайней мере еще один путь. Рассмотрим любой из таких путей. Тактика волка будет заключаться в том, чтобы на любом из ребер, которое принадлежит пути, поставить противоположное направление по отношению к AB. Покажем, что такая тактика является для волка непроигрышной. То есть докажем, что после хода волка граф останется правильным. Предположим противное. Пусть из некоторой вершины X нельзя добраться до вершины Y. Рассмотрим два случая:
1) между X и Y есть ребро.
Тогда оно ориентировано. Поскольку волк следует тактике, то волк только что поставил одностороннее движение на XY. Но XY, согласно тактике, является частью пути между какими-то вершинами (пусть M и N). M и N друг для друга достижимы, точно так же M достижимо для X, а N для Y (без ограничения общности). Пусть из X можно добраться в Y (по ребру между ними), тогда добравшись из Y в N, а там из N в M, а из M в X мы доберемся из Y в X, тогда X и Y взаимно достижимы, противоречие.
2) между X и Y нет ребра.
Точно так же, XY - часть какого-то пути между двумя вершинами. Путь между XY состоит из взаимно достижимых вершин, соединенных ребрами ( доказано в 1) ). Значит, и X и Y взаимно достижимы, противоречие.
Итак, данная тактика является непроигрышной. Пусть волк не будет действовать по этой тактике. Тогда по этой тактике будет действовать лиса, а, значит, волк будет действовать по невыигрышной тактике (что называется неправильная игра). Пусть тогда волк будет действовать волк. Но тогда точно так же придется поступить и лисе. Осталось доказать, что лиса не может проиграть первым ходом. Пусть она изменила напр. на каких-то двух вершинах (они соединены ребром). Тогда они взаимно достижимы по второму пути (после хода лисы всего одно ребро ориентировано). Итак, при правильной игре будет ничья.
Несколько шагов, которые я не расписываю:
1) нацепление двоичного логарифма на все 3 куска неравенства
2) преобразование логарифма произведения в сумму логарифмов в левой и правой части, с последующим вычитанием логарифма от 5^к из всех 3 частей
3) подведение всех 3 частей к степени двойки
получаем такое неравенство:
а < 2^(s-k*log_2(5)) < a+1
Теперь сильное утверждение: любое число можно приблизить сколь угодно сильно, используя лишь s-k*log_2(5), увеличивая s и k до нужного порядка.
Тогда мы всегда можем найти такие k и s, что б двойка в оной степени подходила под наше неравенство, ибо мы можем приблизить любую действительную степень, значит и любое число после возведения двойки в эту степень.