ХайдукВикторович wrote: Надо будет подумать...

Вот еще какая задачка, глядя на то решение, пришла мне в голову. Если в незанятые клетки поставить нули, а в занятые - единицы, то получим матрицу из нулей и единиц. Определитель ее будет равен нулю, поскольку в ней есть одинаковые и строки и столбцы. А вот если рассмотреть все матрицы 8х8 из нулей и единиц, то сколько среди них будет матриц с ненулевым определителем?

метод Монте Карло может зевнуть редкие исключения

Sam Sebe wrote: На этот вопрос достаточно легко ответить.
Первую строку можно выбрать 2⁸-1 способами.
2-ю - 2⁸-2¹ способами.
и т.д.
8-ю - 2⁸-2⁷ способами.
Перемножьте эти восемь чисел и будет Вам счастье.

P.S. Про доминошки
Ну уже по приведенному решению видно, что там очень низкая "энтропия", поэтому монтекарлой она вряд ли достижима.

Vladimirovich wrote:
Не знаю, но распределение, что я надыбал за 40 минут, следующее
(возможно, некоторые конфигурации повторяются, я не проверял).
Конфигурация из count = 22 доминошки, увы, не отловлена.

procrastinator wrote:
Я и сам успел кое-куда сходить. Правда, там ответ не всем понравился. ))

Вчера вечером джим мне голову просветлил и понял, что скорее всего наврал. Приведенная формула показывает количество таких матриц с нечетным определителем, а среди матриц с четным, есть наверняка матрицы полного ранга.

джим это хто?

Хайдук wrote: Хотелось-бы чтобы это был gin, но это был gym.

oh ok,

А знаете, я все-таки отловил решение из 22 доминошек, причем другое, не то, что в статье!

Усовершенствовал немного стратегию ограничения случайности и отловил... за 20 секунд! Правда, ради ускорения пришлось пожертвовать нахождением распределения конфигураций - не доводить до конца те из них, которым требуется больше 23-24 доминошек.



Не стал заморачиваться соединять крестики в доминошки, но проверил, что это действительно решение. И это другое решение: достаточно сравнить оба в углах, чтобы убедиться.



Теперь возникает вопрос, сколько существует различных решений?

В программе, что нашла другое решение, была ошибочка. Я исправил ее, и решение... не появилось. Зато нашлось другое решение, еще одно! Итого их пока три.



Определитель тоже 0.

Sam Sebe wrote: Два дополнительных решения можно было получить намного проще, просто повернув доску на 90 и 180 градусов. А если еще рефлексию использовать, или вертикали g и h оригинального решения сдвинуть в средину доски с соответствующей модификацией бывших вертикалей d,e,f. А потом это все покрутить и порефлексировать...

procrastinator wrote:
Не знаю, как это? В первом решении один пустой угол, во втором - два, а в третьем - три. Вращай не вращай. Думаю, есть еще решение с четырьмя пустыми углами и 5-е решение, без пустых углов.

Вот еще две конфигурации из 22 костяшек нашел. Получил также распределение конфигураций (характеризующее по факту стратегию поиска), а заодно посчитал определители соответствующих матриц из нулей и единиц, правда не для всех конфигураций (для всех это долго), а лишь для конфигураций из 23 костяшек.

Смотрите, как красиво получается. Вот тождество

p + q + pq = 1, где q = (1 - p)/(1 + p),

верное для любого 0 < p < 1. В этом смысле число p и число q являются сопряженными друг другу: q = p* и p = q* = (p*)*.

Т.е. мы как бы имеем разные события: одно случается с вероятностью p, другое - с вероятностью q, а вместе, одновременно, они случаются с вероятностью, равной произведению pq.

Пусть теперь мы наблюдаем и подсчитываем события на практике. Одно событие произошло P раз, другое - Q раз, а вместе они произошли PQ раз (PQ здесь не произведение P и Q, а просто обозначение), итого P + Q + PQ = S раз. Эти события не обязаны быть сопряженными в указанном смысле. Ну а если вдруг это выйдет?! Ну, пусть не в точности, а приближенно... Разве это не информация будет?!

Вот, например, как у меня вчера вышло: P = 44, Q = 17 и PQ (обозначение) = 10, соответственно S = 71. Значение p (а тем самым и q) ищем следующей минимизацией по p:

|P/S - p| + |Q/S - q| + |PQ/S - pq| ==> min,

откуда p = P/S = 0.62. Во, золотая пропорция получилась!

А если минимизировать не сумму модулей, а сумму квадратов, то и вовсе получим p = 0.618... .

P.S. Соответственно pS = 44 точно, qS = 16.7 и pqS = 10.3.

Надо сказать, я когда-то пробовал коллекционировать подобные случаи, много насобирал, потом забросил.

Иначе говоря, систематически отмечал реальные случаи деления целого в золотой пропорции, а потом деления меньшей части опять в золотой пропорции, в идеале так:

золотая пропорция плюс ее куб плюс ее четвертая степень,
т.е. золотая пропорция плюс ее квадрат, в сумме единица.

Или примерно так, как вышло выше: 71 = 44 + 17 + 10 (и заметьте, это не числа Фибоначчи).


Владимирович, что скажете? Не математика для чайников?

Кстати, о числах Фибоначчи, последовательность которых вычисляется по рекуррентной формуле "каждое следующее число есть сумма двух предыдущих". В принципе по этой формуле можно получить сколько угодно различных последовательностей - главное, с какой пары чисел начать. Последовательность Фибоначчи начинается с 0 и 1 или с 1 и 1. Еще одна подобная последовательность чисел, именуемых числами Люка, начинается с 2 и 1 или с 1 и 3. И всё. Другие последовательности, получаемые по той же формуле, если и встречаются, то никак не называются, я, во всяком случае, не слышал. Как вы думаете, в чем здесь дело? Почему выделяются именно эти две последовательности, в чем их особая роль?

Sam Sebe wrote:
Я вот понятия не имею. Может какие дополнительные рекуррентные соотношения интересные для них...

Да, я думаю, это потому, что именно через них в явном виде выражается степень n золотой пропорции:

(1.618...)ⁿ = (L_n + 5^1/2F_n)/2,
(0.618...)ⁿ = (-1)ⁿ(L_n - 5^1/2F_n)/2.

А то, для сравнения, что через них в пределе выражается сама золотая пропорция, - это верно не для них одних, конечно.

Sam Sebe wrote:
Ф присутствует в общем решении всех уравнений x_n+2=x_n+1+x_n независимо от начальных условий
Собссно, решение одно
Поэтому частности тут малоудивительны

Присутствует, но только в пределе.

Sam Sebe wrote:
Это неверно

Как неверно? Если x_n+2 = x_n+1 + x_n, то

x_n+2/x_n+1 = 1 + 1/(x_n+1/x_n)

и в пределе Ф = 1 + 1/Ф независимо от x₀ и x₁, если доказать, что предел существует.

Sam Sebe wrote:
Неверно, что только в пределе

Sam Sebe wrote: По всей видимости, Vladimirovich имеет в виду что
x_n=c₁Фⁿ+c₂(-1-Ф)ⁿ,
где константы c₁ и c₂ определяются первыми двумя членами последовательности.

procrastinator wrote: x_n=c₁Фⁿ+c₂(1-Ф)ⁿ, конечно.

Тогда бы уж выписали сразу и обе константы. Я такой формулы не встречал, хотя формулу Бине знаю, конечно. И сразу возникает вопрос, почему тогда формулой Бине называют не эту формулу, а ее частный случай?

Sam Sebe wrote: Да в том то и дело, что "константы" определяются начальными условиями
Здесь очень близкая идет аналогия с дифференциальными уравнениями, в данном случае
x_n+2 = x_n+1 + x_n <=> x''=x'+x

Корни характеристического уравнения будут φ и -1\φ
Поэтому решения всех последовательностей, Фибоначчи, Люка и еще миллиона разных, будут выражены через золотое сечение.

Vladimirovich wrote:
Да никто и не сомневается, что константы не по начальным условиям, а по n. А вот выписать их, решив систему двух уравнений, не помешало бы, вдруг вся ожидаемая там громоздкость сильно упрощается.