|
Anonymous3856
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 30.09.2005
|
|
Сообщений: 352
|
|
|
|
Рейтинг: 76
|
|
Интересная задача
01.05.2011 00:02
|
|
|
Двое играют в следующую игру: сначала первый игрок ставит кубик на ровную поверхность, второй игрок ставит кубик на уже поставленный кубик, затем снова первый игрок ставит кубик на кубик второго игрока. И так далее.
То есть каждый ход игрок должен поставить свой кубик поверх остальных кубиков. Проигрывает тот, кто не может поставить кубик так, чтобы вся конструкция осталась стоять.
В связи с этой игрой возникают два вопроса
1) существуют ли ситуации, в которых один из игроков не может сделать ход?
2) если да, то есть ли у какого-нибудь игрока выигрышная стратегия?
|
|
|
|
|
"Здравый смысл" подсказывает мне что ответы на оба вопроса: нет. Но серьезно я не думал.
|
 Ignorance is Strength |
|
|
Anonymous3856
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 30.09.2005
|
|
Сообщений: 352
|
|
|
|
Рейтинг: 76
|
|
|
А мне подсказывает, что это далеко не очевидно. Ведь не только третий кубик должен стоять на втором, но второй и третий вместе взятые на первом. И так далее. Условий не так мало.
|
|
|
Postrel
|
|
member
|
|
|
|
|
|
|
Рег.: 19.03.2009
|
|
Сообщений: 101
|
|
|
|
Рейтинг: 150
|
|
|
Если выигрышная стратегия и существует, то у второго игрока.
Пусть выигрышная стратегия существует. Предположим, что у первого игрока. Он ставит первый кубик. Тогда второй игрок, поставив кубик ровно на первый кубик, становится "первым игроком". С этого момента у него тоже есть выигрышная стратегия. Противоречие.
|
|
|
AleXXL
|
|
замкомвзвода
|
|
|
|
|
|
|
Рег.: 09.04.2005
|
|
Сообщений: 506
|
|
|
|
Рейтинг: 527
|
|
|
1) существует, пример писать долго, но смысл в том что можно сильно сместить место установки кубика, так что при любой постановке все будет сваливаться с первого кубика
2) выигрышной стратегии нет, т.к. у каждого есть беспроигрышная стратегия ставить кубик ровно над первым, тогда конструкция всегда на вашем ходе будет устойчива
|
|
|
FrauSoboleva
|
|
Don't Quixote
|
|
|
|
|
|
|
Рег.: 20.11.2004
|
|
Сообщений: 28501
|
|
|
|
Рейтинг: 9798
|
|
Re: Интересная задача
[re: AleXXL]
01.05.2011 00:35
|
|
|
В ответ на:
2) выигрышной стратегии нет, т.к. у каждого есть беспроигрышная стратегия ставить кубик ровно над первым, тогда конструкция всегда на вашем ходе будет устойчива
Мм, а в шахматах у каждого игрока есть беспроигрышная стратегия ходить конем взад-вперед. Если и второй будет так делать, то будет ничья.
|
How much wood would woodchuck chuck, if a woodchuck could chuck wood |
|
|
|
|
В ответ на:
м, а в шахматах у каждого игрока есть беспроигрышная стратегия ходить конем взад-вперед. Если и второй будет так делать, то будет ничья.
WAT?
можно пояснить поподробней?
|
|
|
Postrel
|
|
member
|
|
|
|
|
|
|
Рег.: 19.03.2009
|
|
Сообщений: 101
|
|
|
|
Рейтинг: 150
|
|
|
Выигрышной стратегии не существует.
Так как выигрышная стратегия может быть только у второго игрока (как показано выше), то докажем, что у первого игрока есть стратегия непроигрыша, то есть он сможет поставить любое количество кубиков, какая бы стратегия не использовалась вторым игроком.
Стратегия непроигрыша первого игрока проста: нужно всего лишь всегда ставить свой кубик ровно над своим первым кубиком. Устойчивость башенки выражается серией неравенств. Из этих условий устойчивости башенки после какого-то хода второго игрока можно получить, что следующий ход первого игрока (согласно его стратегии) также приведет к устойчивой башенке (индукция).
Таким образом, выигрышной стратегии не существует, но может оказаться, что проигрывает тот, кто первый поставит свой кубик неровно.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
нет, ну столько очевидного текста, а про самое интересное - два слова ('серия неравенств') 
|
|
|
FrauSoboleva
|
|
Don't Quixote
|
|
|
|
|
|
|
Рег.: 20.11.2004
|
|
Сообщений: 28501
|
|
|
|
Рейтинг: 9798
|
|
|
В ответ на:
Так как выигрышная стратегия может быть только у второго игрока (как показано выше), то докажем, что у первого игрока есть стратегия непроигрыша, то есть он сможет поставить
Как-то это все неправдоподобно.
Вот, скажем, поставил я второй кубик на ребро вот так <>
Причем не прямо по центру, а чуть сдвинул вбок. Тогда первый по этой стратегии ставит кубик прямо над первым и тот падает, соскальзывая по второму.
|
How much wood would woodchuck chuck, if a woodchuck could chuck wood |
|
|
|
|
В ответ на:
Вот, скажем, поставил я второй кубик на ребро вот так <>
Ага ты еще не вершину поставь, это все таки вырожденный случай видимо не включенный в рассмотрение.
|
Ignorance is Strength |
|
|
Postrel
|
|
member
|
|
|
|
|
|
|
Рег.: 19.03.2009
|
|
Сообщений: 101
|
|
|
|
Рейтинг: 150
|
|
|
Пусть ![[math]$$X_{i}$$[/math]](mathimg.php?math=%24%24X_%7Bi%7D%24%24) - координаты центров кубиков в системе координат, связаной с первым кубиком( ![[math]$$X_1=0$$[/math]](mathimg.php?math=%24%24X_1%3D0%24%24) ). Кубики пронумерованы с основания. Сторону кубика возьмем равной 2. Стратегия первого игрока - ![[math]$$X_{2i+1}=0$$[/math]](mathimg.php?math=%24%24X_%7B2i%2B1%7D%3D0%24%24) . Второй игрок ходит последовательностью ![[math]$$X_{2i}$$[/math]](mathimg.php?math=%24%24X_%7B2i%7D%24%24) , произвольной, но лишь бы на его ходе башенка устояла.
Устойчивость системы из ![[math]k[/math]](mathimg.php?math=k) кубиков выражается неравенствами. Каждое есть факт того, что центр масс всех кубиков без ![[math]j[/math]](mathimg.php?math=j) первых находится над кубиком, ![[math]$$0<=j<=k$$[/math]](mathimg.php?math=%24%240%26lt%3B%3Dj%26lt%3B%3Dk%24%24) .
![[math]$$|X_k-X_{k-1}|<=1$$[/math]](mathimg.php?math=%24%24%7CX_k-X_%7Bk-1%7D%7C%26lt%3B%3D1%24%24)
![[math]$$|(X_k+X_{k-1})/{2}-X_{k-2}|<=1$$[/math]](mathimg.php?math=%24%24%7C%28X_k%2BX_%7Bk-1%7D%29%2F%7B2%7D-X_%7Bk-2%7D%7C%26lt%3B%3D1%24%24)
..
![[math]$$|(X_{k}+... +X_{j+1})/(k-j)-X_{j}|<=1$$[/math]](mathimg.php?math=%24%24%7C%28X_%7Bk%7D%2B...%20%2BX_%7Bj%2B1%7D%29%2F%28k-j%29-X_%7Bj%7D%7C%26lt%3B%3D1%24%24)
..
![[math]$$|(X_k+...+X_{1})/{k}|<=1$$[/math]](mathimg.php?math=%24%24%7C%28X_k%2B...%2BX_%7B1%7D%29%2F%7Bk%7D%7C%26lt%3B%3D1%24%24)
Другими словами, самый верхний кубик не упадет с предидущего, два самых верхних как целое не упадут с третьего с конца кубика и так далее.
Теперь надо предположить, что второй игрок сделал ход и башенка устояла. Второй сделает свой ход, , и условия устойчивости его новой башенки являются следствиями условий устойчиовсти башенки второго игрока. Надо чуть-чуть помучится, важное следствие, например, что все ![[math]$$|X_{2i}|<=1$$[/math]](mathimg.php?math=%24%24%7CX_%7B2i%7D%7C%26lt%3B%3D1%24%24) .
Редактировал Postrel (01.05.2011 13:14)
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
надо просто потребовать устойчивость или хотя бы безразличность положения равновесия, иначе плохо
|
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
|
Контрпример:
Edit: Сорри, неправильно прочитал.
|
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Update. Липа. Ниже правильный пример.
1).
2). уже ответили.
Редактировал Pooh (01.05.2011 13:46)
|
|
|
Postrel
|
|
member
|
|
|
|
|
|
|
Рег.: 19.03.2009
|
|
Сообщений: 101
|
|
|
|
Рейтинг: 150
|
|
|
Почему же? Включить можно и эти случаи, но такие постановки неустойчивы, так что любой, кто поставит на ребро или вершину, проиграет.
|
|
|
Postrel
|
|
member
|
|
|
|
|
|
|
Рег.: 19.03.2009
|
|
Сообщений: 101
|
|
|
|
Рейтинг: 150
|
|
Re: Интересная задача
[re: Pooh]
01.05.2011 12:53
|
|
|
Если это пример того, когда нельзя сделать никакой ход, то он некорректен. Второй с верхушки кубик, сам по себе, без самого верхнего - неустойчив.
|
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Точно. Слажал 
|
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
Re: Интересная задача
[re: Pooh]
01.05.2011 13:21
|
|
|
Во как!
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
ну и еще наверняка не учтено, что можно поворачивать кубики вдоль вертикальной оси
|
|
Список
Плоский
Дерево
