Игра на доске 10x10

[lel0lel]

vicvolf в сообщении #1679527 писал(а):

Просто хотел сказать, что на части шахматной доски 2х10 числа могут быть расположены в виде "змейки", а на другой части 8х10 они могут быть расположены по-другому. Тогда у короля может быть маршрут с суммой меньше 500

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

Сможете показать, что в любой таблице 10×10 всегда найдется полоса с суммой всех чисел не превосходящей 1010? Это требуется, чтобы завершить доказательство)

[vicvolf]

lel0lel в сообщении #1679603 писал(а):

Сможете показать, что в любой таблице 10×10 всегда найдется полоса с суммой всех чисел не превосходящей 1010? Это требуется, чтобы завершить доказательство)

Здесь же сумма чисел на доске всегда 5050, поэтому среднее по строке - 505. А стратегия "змейка" в каждой строке и дает 505. Она соответствует принципу Дирихле.

[Alex Krylov]

Выше вот нечто такое мной было написано:

Цитата:

Условия непрерывности траекторий (вроде такое имеет смысл):
$\\ \sum\limits_{i=1}^{N-1}(Y_{i,j+1}+Y_{i+1,j})+\sum\limits_{i=1}^{N-1}(Y_{i+1,j+1}+Y_{i,j})+\sum\limits_{i=1}^{N}(Y_{i,j}+Y_{i,j+1})=2 \\ \forall j =1,\dots,N-1 $

Это туфта. "Условия непрерывности траекторий" относительно переменных $Y_{i,j}$ невыпуклы, а значит тот подход, о котором говорилось выше (взяли, релаксировали булевы ограничения на $Y_{i,j}$, как единственные невыпуклые ограничения), утрачивает основания.