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

[mavoumuro]

Петя и вася играют в следующую игру.
Вася заполняет числами от 1 до 100 клетки таблицы 10x10. ( каждое по одному разу )
Петя хочет пройти шахматным королем от левого края доски до правого. При этом, если он ставит короля на какую ту клетку, то он должен заплатить Васе то число рублей что записанно в клетке, сколько Петя заплатит Васи при правильной игре ? ( Вася хочет заработать как можно больше, Петя заплатить как можно меньше )

[wrest]

mavoumuro в сообщении #1678842 писал(а):

сколько Петя заплатит Васи при правильной игре ?

На первый взгляд, не менее 581.

[lel0lel]

Стоит ли шахматный король на доске? Или Васе нужно представить оптимальную матрицу (указав начальную сторону Пете), для которой самая дешёвая прогулка Пети не будет дешевле самой дешёвой прогулки в любой другой матрице? То есть, матрицу, максимизирующую минимально возможный доход.

[wrest]

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

То есть, матрицу, максимизирующую минимально возможный доход.

Я так понял, что да. В общей постановке, король не стоит на доске, первым ходом начинать можно с любой клетки, но обязательно посетить первый и затем последний столбцы (так что лучше сразу ходить сначала в первый).

[zgemm]

wrest в сообщении #1678846 писал(а):

mavoumuro в сообщении #1678842 писал(а):

сколько Петя заплатит Васи при правильной игре ?

На первый взгляд, не менее 581.

У меня тоже примерно 590 получилось, но как доказать точно пока не могу. А Вы как решали? Моя идея - на диагонали поставить максимально большие числа, а далее - чем дальше от диагонали, тем меньше.

[wrest]

zgemm в сообщении #1678852 писал(а):

А Вы как решали? Моя идея - на диагонали поставить максимально большие числа, а далее - чем дальше от диагонали, тем меньше.

Я змейкой расставил, типа
1 8 09 16
2 7 10 15
3 6 11 14
4 5 12 13


P.S. Нашел у себя ошибку (было 11 столбцов а не 10). "Змейкой" получается 500 (при сумме каждой строки в 505).

[lel0lel]

zgemm в сообщении #1678853 писал(а):

Моя идея - на диагонали поставить максимально большие числа, а далее - чем дальше от диагонали, тем меньше.

Что-то этот метод не даёт оптимальную таблицу для случая 2*2, а вот змейка даёт.

[mavoumuro]

wrest в сообщении #1678853 писал(а):

zgemm в сообщении #1678852 писал(а):

А Вы как решали? Моя идея - на диагонали поставить максимально большие числа, а далее - чем дальше от диагонали, тем меньше.

Я змейкой расставил, типа
1 8 09 16
2 7 10 15
3 6 11 14
4 5 12 13


P.S. Нашел у себя ошибку (было 11 столбцов а не 10). "Змейкой" получается 500 (при сумме каждой строки в 505).

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

[zgemm]

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

zgemm в сообщении #1678853 писал(а):

Моя идея - на диагонали поставить максимально большие числа, а далее - чем дальше от диагонали, тем меньше.

Что-то этот метод не даёт оптимальную таблицу для случая 2*2, а вот змейка даёт.

Почему же, давайте расставим

$$\begin{tabular}{cc} 1 & 4 \\ 3 & 2 \\ \end{tabular}$$

Очевидно, что самый короткий путь как не крути - $3+4$, а если мы по пути забежали на $1$ или $2$, то второму игроку это не выгодно. Может под диагональю мы с Вами разные вещи понимали - я понимаю диагональ, по которой будет самый короткий путь.

[wrest]

zgemm в сообщении #1678877 писал(а):

Почему же, давайте расставим

$$\begin{tabular}{cc} 1 & 4 \\ 3 & 2 \\ \end{tabular}$$

Тут минимум стоимость 3. Сравните теперь с

$$\begin{tabular}{cc} 1 & 4 \\ 2 & 3 \\ \end{tabular}$$

Тут минимальная стоимость 4.

[mihaild]

zgemm в сообщении #1678877 писал(а):

Очевидно, что самый короткий путь как не крути - $3+4$

Нас же просят дойти от левого края до правого, а не от левой нижней клетки до правой верхней.

[zgemm]

mihaild в сообщении #1678881 писал(а):

Нас же просят дойти от левого края до правого, а не от левой нижней клетки до правой верхней.

ой, точно, спасибо! Я условие не так понял и не ту задачу решал.

[mihaild]

Итого пока оценка сверху 505, оценка снизу 500. Точнее пока не получается. Для случайной расстановки чуть больше 200.

[12d3]

Рассмотрим горизонтальную полоску 2х10 с наименьшей суммой, которая не превосходит 1010. Выбирая в каждом столбике из двух клеток наименьшее число, получим путь с суммой, не превосходящей $\frac{1010 - 10}{2} = 500$.

[vicvolf]

Данная задача является антагонистической игрой (игрой с нулевой суммой). В антагонистических играх оптимальное решение определяется равновесием Нэша, где: минимаксное значение=максиминное значение, минимаксное значение=максиминное значение.
Стратегия Васи: Для максимизации минимальной суммы, которую заплатит Петя, Вася равномерно распределяет числа так, чтобы в каждом столбце находились числа из определённого диапазона:
В первом столбце: $1-10$ (минимальное число — $1$),
Во втором столбце: $11-20$ (минимальное — $11$),
...
В десятом столбце: $91-100$ (минимальное — $91$).
Стратегия Пети: Петя выбирает путь, проходящий через минимальные числа каждого столбца. Такой путь гарантирует минимальную сумму, так как обойти эти числа невозможно из-за равномерного распределения.
Расчёт суммы: Сумма минимальных чисел в каждом столбце:
$1+11+21+31+41+51+61+71+81+91=460$
Таким образом, при оптимальной стратегии обоих игроков минимальная сумма, которую Петя обязан заплатить, составляет $460$ рублей.