|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
| iourique:Пункт 1) несложный - М(2p)= 5(p-1). |
Несложный. Обязательные повороты будут:
1) на всех клетках, расположенных на краю доски, за исключением двух, в которых можно начинать и заканчивать маршрут = 4p-2-2 = 4(p-1)
2) на некраевых клетках = p-1 (любой ход слона может принадлежать только одной из р фигур : большая диагональ + р-1 прямоугольников, переходы от одной к другой = р-1)
итого: 4(р-1)+р-1=5(р-1)
iourique: | iourique: Пункт 2) я пока не просек - последовательность 1,11,32 как-то не внушает энтузиазма... |
Появилась рабочая гипотеза: L(2p) = (11*p*p - 13*p + 4)/2, достижимое p!/2 различными способами.
p.s. доказал. |
а хотя бы приблизительно ход рассуждений?
ps. у меня получается, что кол-во несимметричных способов = (р-1)! |
|
|
| номер сообщения: 49-2-2648 |
|
|
|
|
| azur: ps. у меня получается, что кол-во несимметричных способов = (р-1)! |
(маршруты считал без учёта направления прохода) |
|
|
| номер сообщения: 49-2-2649 |
|
|
|
|
azur:
iourique: | iourique: Пункт 2) я пока не просек - последовательность 1,11,32 как-то не внушает энтузиазма... |
Появилась рабочая гипотеза: L(2p) = (11*p*p - 13*p + 4)/2, достижимое p!/2 различными способами.
p.s. доказал. |
а хотя бы приблизительно ход рассуждений?
ps. у меня получается, что кол-во несимметричных способов = (р-1)! |
Приблизительно так: обход 4 углов каждого из (p-1) прямоугольников - это (2p-1)+ k ходов, где k+1 - длина длинной стороны. Обход двух углов диагонали - (2p-1) ход. Перескок с одного прямоугольника на другой - тоже (2p-1), если считать от угла до угла.
Количество маршрутов равно числу способов упорядочить прямоугольники - р! - ну и пополам, так как можно идти как слева направо, так и справа налево. Других симметрий не вижу, если честно. |
|
|
| номер сообщения: 49-2-2650 |
|
|
|
|
iourique: azur:
ps. у меня получается, что кол-во несимметричных способов = (р-1)! |
... Количество маршрутов равно числу способов упорядочить прямоугольники - р! - ну и пополам, так как можно идти как слева направо, так и справа налево. Других симметрий не вижу, если честно. |
хмм .. кол-во прямоугольников = р-1 (начинать либо заканчивать маршрут приходится в углу на большой диагонали), число их перестановок = (р-1)!
вроде так .. |
|
|
| номер сообщения: 49-2-2651 |
|
|
|
|
| azur:(начинать либо заканчивать маршрут приходится в углу на большой диагонали) |
Почему? Чем плох такой маршрут на доске 6х6: a3-d6-f4-c1-b2-f6-a1-d4-b6-f2-e1-a5?
э-э, значит их еще больше - с диагонали можно свалиться в две стороны - кроме a3-d6-f4-c1-b2-f6-a1-d4-b6-f2-e1-a5 есть еще и a3-d6-f4-c1-b2-f6-a1-d4-f2-b6-a5-e1. Тогда вроде получается (р-1)! + (р!-2*(р-1)!) = р!-(р-1)!. |
|
|
| номер сообщения: 49-2-2652 |
|
|
|
|
iourique: | azur:(начинать либо заканчивать маршрут приходится в углу на большой диагонали) |
Почему? Чем плох такой маршрут на доске 6х6: a3-d6-f4-c1-b2-f6-a1-d4-b6-f2-e1-a5? |
упс, и правда ..
непонятно откуда прилетел ко мне этот глюк  |
|
|
| номер сообщения: 49-2-2653 |
|
|
|
|
Получается интересная закономерност для Lmah:
...n= ----2----4----6----8---10---12---14---16---18
Lmah= ----1---11---32---64--107--161--226--302--389(?)
Lmah 1..+10..+21..+32..+43..+54..+65..+76..+87(?) "-Пахнет литром,но доказат не могу!" (Чапаев)  |
|
|
| номер сообщения: 49-2-2654 |
|
|
|
|
| peBu3op: Перед котом Леопольдом 5 норок. В одной из норок сидит мышка. Кот наугад может запустить 1 лапу в 1 норку. Мышка трусливая - поэтому после каждого раза, когда кот сует лапу она перебегает в соседнюю норку. Может ли кот ее поймать? |
А если норок 6? |
|
|
| номер сообщения: 49-2-2655 |
|
|
|
|
| Юрик, Вы меня не поняли :-) |
|
|
| номер сообщения: 49-2-2656 |
|
|
|
|
Я собственно имел ввиду, что задача некорректно сформулирована. Прежде всего ясно, что кот может запустить лапу сразу в нужную норку :-) - потому и "может".
Ну, это конечно придирка :-) - чего хотел автор ясно, Но есть и возражение по существу - например, норки по прямой или в круг? Априори неясно, важно ли это. |
|
|
| номер сообщения: 49-2-2658 |
|
|
|
|
| Grigoriy: Ну, это конечно придирка :-) - чего хотел автор ясно, Но есть и возражение по существу - например, норки по прямой или в круг? Априори неясно, важно ли это. |
Задачка сформулирована не ахти, это правда. Норки по прямой (иначе неинтересно). Мышка перебегает после того, как кот вытащил лапу - в частности, может перебежать именно туда, куда он ее только что совал. |
|
|
| номер сообщения: 49-2-2659 |
|
|
|
|
iourique: | Grigoriy: Ну, это конечно придирка :-) - чего хотел автор ясно, Но есть и возражение по существу - например, норки по прямой или в круг? Априори неясно, важно ли это. |
Задачка сформулирована не ахти, это правда. Норки по прямой (иначе неинтересно). Мышка перебегает после того, как кот вытащил лапу - в частности, может перебежать именно туда, куда он ее только что совал. |
Ну, тогда просто. Надо заметить - мышка каждый "ход" меняет место с четного на нечетное, и наоборот.
Начинаем с норок 2, 3, 4, в этом порядке. Эта последовательность гарантирует поймать мышь если она была сначала в четной норке (2 или 4). Если не поймали - значит, мышь начала с нечетной норки, а в данный момент (после трёх ходов) находиться в четной. Ну, как решать чётную норку, мы уже знаем - те же 2,3,4. То есть, 2,3,4,2,3,4, и всё. |
|
|
| номер сообщения: 49-2-2660 |
|
|
|
|
| Zdrak: То есть, 2,3,4,2,3,4, и всё. |
Очень изящно - гораздо чище, чем мое решение. И приятно, что оно без изменений обобщается на случай произвольного числа дырок. |
|
|
| номер сообщения: 49-2-2661 |
|
|
|
|
| номер сообщения: 49-2-2662 |
|
|
|
|
К задаче о изопериметрической точке
MikhailK:Раз уж я потратил столько времени на эту задачу, то мне захотелось посмотреть литературу по этому вопросу. Пролистав несколько статей я отложил вот эту для более внимательного чтения
Central Points and Central Lines in the Plane of a Triangle
Clark Kimberling
Mathematics Magazine, Vol. 67, No. 3 (Jun., 1994), pp. 163-187
Желающим могу прислать PDF этой статьи. |
Я в восторге от этой статьи. Там перечислены более сотни знаменитых (и не очень) точек треугольника, приведены их координаты. Если некоторые из перечисленных точек лежат на одной прямой, то это также отмечено. В списке также присутствует и изопериметрическая точка, но она попала почему-то в перечень нерегулярных точек. Причина этого мне пока не очень ясна.
Ого, оказалось, что автор статьи создал энциклопедию интересных точек в треугольнике. Там их тысячи. |
|
|
| номер сообщения: 49-2-2663 |
|
|
|
|
| Как думаете, сколько шахов подряд могут объявить белые и черные друг другу во время шахматной партии? |
|
|
| номер сообщения: 49-2-2666 |
|
|
|
|
| azur: Как думаете, сколько шахов подряд могут объявить белые и черные друг другу во время шахматной партии? |
Завёл "consecutive checks" в Гугль. Оказалось, рекорд в шахматной композиции: 51 шахов подряд.
www.xs4all.nl/~timkr/chess2/diary.htm |
|
|
| номер сообщения: 49-2-2667 |
|
|
|
|
iourique: | Zdrak: То есть, 2,3,4,2,3,4, и всё. |
Очень изящно - гораздо чище, чем мое решение. И приятно, что оно без изменений обобщается на случай произвольного числа дырок. |
Правильно я понимаю, что при круговом расположении норок мышку поймать нельзя? |
|
|
| номер сообщения: 49-2-2668 |
|
|
|
|
MikhailK: iourique: | Zdrak: То есть, 2,3,4,2,3,4, и всё. |
Очень изящно - гораздо чище, чем мое решение. И приятно, что оно без изменений обобщается на случай произвольного числа дырок. |
Правильно я понимаю, что при круговом расположении норок мышку поймать нельзя? |
Нутром чую что нельзя, а доказывать лень  |
|
|
| номер сообщения: 49-2-2669 |
|
|
|
|
Zdrak: MikhailK: iourique: | Zdrak: То есть, 2,3,4,2,3,4, и всё. |
Очень изящно - гораздо чище, чем мое решение. И приятно, что оно без изменений обобщается на случай произвольного числа дырок. |
Правильно я понимаю, что при круговом расположении норок мышку поймать нельзя? |
Нутром чую что нельзя, а доказывать лень |
Это несложно. Меня решения Zdrak'а натолкнуло на такую интерпретацию задачи: есть шахматная доска размера n на m. Первый игрок отмечает по клетке на каждом ряду. После этого второй игрок ставит слона на произвольную клетку первой горизонтали и пытается провести его на последнюю горизонталь, не проходя через отмеченные клетки. Кто выиграет при правильной игре?
В этой интерпретации дырки по кругу - это цилиндрическая доска, на которой у слона всегда есть два хода, из которых только один может быть заблокирован. Так что выигрывает второй - мышка не ловится. |
|
|
| номер сообщения: 49-2-2670 |
|
|
|
|
iourique: Меня решения Zdrak'а натолкнуло на такую интерпретацию задачи: есть шахматная доска размера n на m. Первый игрок отмечает по клетке на каждом ряду. После этого второй игрок ставит слона на произвольную клетку первой горизонтали и пытается провести его на последнюю горизонталь, не проходя через отмеченные клетки. Кто выиграет при правильной игре?
|
Если на каждой из горизонталей и вертикалей должно быть не больше одной отмеченной клетки, то можно "перекрыть кислород" слону только, наверно, заранее зная какого он будет цвета
(для этого достаточно отметить подряд по диагонали n-2 клеток, если n - число вертикалей) |
|
|
| номер сообщения: 49-2-2672 |
|
|
|
|
azur: iourique: Меня решения Zdrak'а натолкнуло на такую интерпретацию задачи: есть шахматная доска размера n на m. Первый игрок отмечает по клетке на каждом ряду. После этого второй игрок ставит слона на произвольную клетку первой горизонтали и пытается провести его на последнюю горизонталь, не проходя через отмеченные клетки. Кто выиграет при правильной игре?
|
Если на каждой из горизонталей и вертикалей должно быть не больше одной отмеченной клетки, то можно "перекрыть кислород" слону только, наверно, заранее зная какого он будет цвета
(для этого достаточно отметить подряд по диагонали n-2 клеток, если n - число вертикалей) |
Осталось повторить два раза и будет аккурат решение Zdrak'а. |
|
|
| номер сообщения: 49-2-2674 |
|
|
|
|
Решил сюда перенести:
| Roger: Мне кажется, современными процессорными фермами можно обсчитать 30 полуходов из начальной позиции за разумно-ограниченное время. |
| Хайдук:Скорее всего такое неверно - мат в 15 ходов или меньше нашли бы за всю историю шахмат. |
Посчитать, наверно, можно, и да, разумеется, черные могут продержаться 15 ходов, причем почти как угодно. Я собственно хотел (а) подчеркнуть разницу между человеческим восприятием и математическим/компьютерным подходом; (б) задаться таким вопросом - очевидно, любой из здесь присутствующих продержится 15 ходов против кого угодно. При каком числе ходов эта задача становится нетривиальной? |
|
|
| номер сообщения: 49-2-2677 |
|
|
|
|
Попытался изучить вопрос, сколько существует шахматных позиций, и не нашел никаких приличных оценок. Разброс от 10^43 до 10^50. Откуда берется 10^50 я приблизительно понимаю:
64*63*Sum[
Binomial[48, wp] Sum[
Binomial[48 - wp, bp] Sum[
Binomial[62 - wp - bp, w] 4^w Sum[
Binomial[62 - wp - bp - w, b] 4^b, {b, 0, 15 - bp}],
{w, 0, 15 - wp}], {bp, 0, 8}], {wp, 0, 8}] =
= 75626417639907102049332398462492933177069830824768.
(Здесь сначала выбирается клетка для белого короля, потом для черного [тут, кстати, 63 можно заменить на 60, но для порядка величины это несущественно], потом из 48 клеток не на первом и последнем ряду выбирается место для нескольких [от 0 до 8] белых пешек [wp] и нескольких черных [bp], а из оставшихся полей [62 - wp - bp] несколько [от 0 до 15 - wp] мест для белых фигур, каждая из которых может быть ладьей, слоном, конем или ферзем, и то же самое для черных фигур.)
С оценкой 10^43 хуже. Если я правильно догадываюсь она берется из следующей формулы:
64!/(32! (8!)^2 (2!)^6) =
= 4634726695587809641192045982323285670400000.
Тут мы выбираем 32 клетки на которых стоят фигуры, считая все фигуры различными [64!/32!], а потом допускаем перестановки пешек [8!^2], слонов, коней и ладей [2!^6]. Но это, кажется, идиотизм, потому что мы считаем исключительно 32-фигурные позиции и те неправильно - их на самом деле гораздо меньше. Так как не было никаких взятий, пешки заперты на своих вертикалях, так что есть всего 15^8 способов их расстановки. Из оставшихся 48 клеток уже можно выбирать места для 16 фигур как указано выше. Получается
15^8 48!/32!/(2^6) =
= 1889240032069413663665025000000000,
число порядка 10^33.
Кто-нибудь знает что-нибудь получше? |
|
|
| номер сообщения: 49-2-2678 |
|
|
|
|
| номер сообщения: 49-2-2679 |
|
|
|
|
Оценка Литтлвуда удручает. Довольно сложным рассуждением он показывает, что число позиций не превосходит 10^69, хотя лучший результат достигается в одну строчку - 64 * 63 [короли] * 11^62 [на каждой из остальных клеток могут быть 5 белых или 5 черных фигур или ничего], т.е. число порядка 10^68. |
|
|
| номер сообщения: 49-2-2680 |
|
|
|
|
| А как учитываются позиции с предысторией (рокировки и пешки на проходе)? |
|
|
| номер сообщения: 49-2-2681 |
|
|
|
|
| Roger: А как учитываются позиции с предысторией (рокировки и пешки на проходе)? |
Я вполне сознательно их не считал: достаточно ясно, что все эти тонкости могут увеличить число позиций не больше, чем на порядок, что явно находится в пределах погрешности. Но если хотеть честную оценку сверху - надо будет считать.
Кстати, в такой партии 1. h3 Nf6 2. Rh2 Ng8 3. Rh1 Nf6 4. Rh2 Ng8 5. Rh1 - уже можно требовать ничью или еще нет? |
|
|
| номер сообщения: 49-2-2682 |
|
|
|
|
| Удается, кажется, еще порядок-другой сбросить. Я уже писал, что 32-фигурных позиций относительно немного (10^34). По тем же причинам не очень много 31-фигурных позиций (очень грубая оценка дает 10^42). Соответственно для оценки общего числа позиций достаточно считать позиции с не более чем 30 фигурами, а их число можно ограничить сверху чем-то вроде 10^48. |
|
|
| номер сообщения: 49-2-2685 |
|
|
|
|
Другой забавный вопрос - число возможных шахматных партий. Литтлвуд оценивает его так. Сначала оценим число N возможных позиций (у Литтлвуда выходит 10^70, но мы уже знаем, что есть оценка 10^50). Потом число возможных ходов в позиции. Литтлвуд что-то считает, хотя и очень грубо, но можно поступить совсем нечутко: ходят k <= 16 фигур и пойти они могут на одну из 64-k незанятых ими клеток. Т.е, у них всего не более чем k(64-k)<=16*48=758 ходов. Поскольку больше чем 2N ходов в партии быть не может (какая-нибудь позиция повторится трижды), то всего партий не больше чем 758^2N = exp(2N*ln(758)) (отсюда видно, почему оценка числа возможных ходов в позиции не очень важна - на фоне гигантского числа N, ln(758) блекнет).
Я немного подумал о том, как эту оценку можно было бы улучшить. Пока есть одна конструктивная идея. Всего в легальных позициях возможно порядка 10^16 различных пешечных структур:
Sum[Binomial[48, wp] Sum[Binomial[48 - wp, bp], {bp, 0, 8}], {wp, 0, 8}]
= 49095495585283107.
(Тут я опять из 48 полей, доступных для пешек, выбираю несколько полей для белых пешек, а из оставшихся - несколько полей для черных. К сожалению, не все получающиеся структуры легальны - например, не может быть 6 белых пешек на одной вертикали, если все черные пешки целы - но, по ощущениям, порядок величины это должно менять не очень сильно (?).)
Однако в партии может встретиться не более 97 разных пешечных структур (новая пешечная структура возникает, когда пешка ходит или ее съедают - в жизни каждой пешки не более 6 таких событий). Отсюда следует (?), что число позиций, которые могут встретиться в одной партии, меньше чем N где-то на 12-14 порядков. Если это так, то это - серьезное улучшение.
p.s. Еще на несколько порядков экспоненту можно скостить, глядя на набор фигур на доске. Всего разных наборов около 75 миллионов, а в партии встречается не более 47 (= 15*2[взятие] + 8*2 [проход в ферзи] + 1[начальный]) наборов.
p.p.s. Мы, разумеется, не пользуемся правилом 50 ходов. |
|
|
| номер сообщения: 49-2-2686 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2024 гг. |
|
|
|
