Ключевое слово
28 | 03 | 2024
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: Математика для Чайников №4

Математика для Чайников №4 22 Июль 2019 19:39 #181

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
ХайдукВикторович wrote:
Такие задачи обычно решаются методом динамического програмирования.
Надо будет подумать...

Вот еще какая задачка, глядя на то решение, пришла мне в голову. Если в незанятые клетки поставить нули, а в занятые - единицы, то получим матрицу из нулей и единиц. Определитель ее будет равен нулю, поскольку в ней есть одинаковые и строки и столбцы. А вот если рассмотреть все матрицы 8х8 из нулей и единиц, то сколько среди них будет матриц с ненулевым определителем?
Сам себе доктор наук
Last Edit: 22 Июль 2019 19:40 by Sam Sebe.

Математика для Чайников №4 22 Июль 2019 20:54 #182

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
метод Монте Карло может зевнуть редкие исключения :flag:

Математика для Чайников №4 22 Июль 2019 21:13 #183

  • procrastinator
  • procrastinator's Avatar
Sam Sebe wrote:
А вот если рассмотреть все матрицы 8х8 из нулей и единиц, то сколько среди них будет матриц с ненулевым определителем?
На этот вопрос достаточно легко ответить.
Первую строку можно выбрать 28-1 способами.
2-ю - 28-21 способами.
и т.д.
8-ю - 28-27 способами.
Перемножьте эти восемь чисел и будет Вам счастье.

Математика для Чайников №4 23 Июль 2019 04:04 #184

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
P.S. Про доминошки
Ну уже по приведенному решению видно, что там очень низкая "энтропия", поэтому монтекарлой она вряд ли достижима.
Каждому - своё.
Last Edit: 23 Июль 2019 04:05 by Vladimirovich.

Математика для Чайников №4 23 Июль 2019 04:17 #185

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Vladimirovich wrote:
P.S. Про доминошки
Ну уже по приведенному решению видно, что там очень низкая "энтропия", поэтому монтекарлой она вряд ли достижима.

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

100000000.png
Сам себе доктор наук
Last Edit: 23 Июль 2019 04:25 by Sam Sebe.

Математика для Чайников №4 23 Июль 2019 04:21 #186

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
procrastinator wrote:
На этот вопрос достаточно легко ответить.

Я и сам успел кое-куда сходить. Правда, там ответ не всем понравился. ))
Сам себе доктор наук
Last Edit: 23 Июль 2019 04:22 by Sam Sebe.

Математика для Чайников №4 23 Июль 2019 13:25 #187

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

Математика для Чайников №4 23 Июль 2019 13:36 #188

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
джим это хто? :unsure:

Математика для Чайников №4 23 Июль 2019 13:46 #189

  • procrastinator
  • procrastinator's Avatar
Хайдук wrote:
джим это хто? :unsure:
Хотелось-бы чтобы это был gin, но это был gym.

Математика для Чайников №4 23 Июль 2019 13:54 #190

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
oh ok, :xren:

Математика для Чайников №4 23 Июль 2019 17:47 #191

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
А знаете, я все-таки отловил решение из 22 доминошек, причем другое, не то, что в статье!

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

count-22.png


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

catch-22_2019-07-23.png


Теперь возникает вопрос, сколько существует различных решений?
Сам себе доктор наук
Last Edit: 23 Июль 2019 19:45 by Sam Sebe.

Математика для Чайников №4 24 Июль 2019 10:17 #192

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
В программе, что нашла другое решение, была ошибочка. Я исправил ее, и решение... не появилось. Зато нашлось другое решение, еще одно! Итого их пока три.

third_22.png


Определитель тоже 0.
Сам себе доктор наук
Last Edit: 24 Июль 2019 10:43 by Sam Sebe.

Математика для Чайников №4 24 Июль 2019 13:08 #193

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

Математика для Чайников №4 24 Июль 2019 14:16 #194

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
procrastinator wrote:
Два дополнительных решения можно было получить намного проще, просто повернув доску на 90 и 180 градусов.

Не знаю, как это? В первом решении один пустой угол, во втором - два, а в третьем - три. Вращай не вращай. Думаю, есть еще решение с четырьмя пустыми углами и 5-е решение, без пустых углов.
Сам себе доктор наук
Last Edit: 24 Июль 2019 14:18 by Sam Sebe.

Математика для Чайников №4 25 Июль 2019 04:11 #195

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Вот еще две конфигурации из 22 костяшек нашел. Получил также распределение конфигураций (характеризующее по факту стратегию поиска), а заодно посчитал определители соответствующих матриц из нулей и единиц, правда не для всех конфигураций (для всех это долго), а лишь для конфигураций из 23 костяшек.

4-5th_22.png
Сам себе доктор наук
Last Edit: 25 Июль 2019 04:20 by Sam Sebe.

Математика для Чайников №4 27 Июль 2019 06:14 #196

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Смотрите, как красиво получается. Вот тождество

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.
Сам себе доктор наук
Last Edit: 27 Июль 2019 10:37 by Sam Sebe.

Математика для Чайников №4 27 Июль 2019 06:49 #197

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Надо сказать, я когда-то пробовал коллекционировать подобные случаи, много насобирал, потом забросил.

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

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


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


Владимирович, что скажете? Не математика для чайников?
Сам себе доктор наук
Last Edit: 27 Июль 2019 07:16 by Sam Sebe.

Математика для Чайников №4 27 Июль 2019 13:38 #198

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Кстати, о числах Фибоначчи, последовательность которых вычисляется по рекуррентной формуле "каждое следующее число есть сумма двух предыдущих". В принципе по этой формуле можно получить сколько угодно различных последовательностей - главное, с какой пары чисел начать. Последовательность Фибоначчи начинается с 0 и 1 или с 1 и 1. Еще одна подобная последовательность чисел, именуемых числами Люка, начинается с 2 и 1 или с 1 и 3. И всё. Другие последовательности, получаемые по той же формуле, если и встречаются, то никак не называются, я, во всяком случае, не слышал. Как вы думаете, в чем здесь дело? Почему выделяются именно эти две последовательности, в чем их особая роль?
Сам себе доктор наук

Математика для Чайников №4 27 Июль 2019 15:24 #199

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Sam Sebe wrote:
Почему выделяются именно эти две последовательности, в чем их особая роль?

Я вот понятия не имею. Может какие дополнительные рекуррентные соотношения интересные для них...
Каждому - своё.

Математика для Чайников №4 27 Июль 2019 17:33 #200

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Да, я думаю, это потому, что именно через них в явном виде выражается степень n золотой пропорции:

(1.618...)n = (Ln + 51/2Fn)/2,
(0.618...)n = (-1)n(Ln - 51/2Fn)/2.


А то, для сравнения, что через них в пределе выражается сама золотая пропорция, - это верно не для них одних, конечно.
Сам себе доктор наук
Last Edit: 27 Июль 2019 17:57 by Sam Sebe.

Математика для Чайников №4 27 Июль 2019 18:01 #201

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Sam Sebe wrote:
Да, я думаю, это потому, что именно через них в явном виде выражается степень n золотой пропорции:

Ф присутствует в общем решении всех уравнений xn+2=xn+1+xn независимо от начальных условий
Собссно, решение одно
Поэтому частности тут малоудивительны
Каждому - своё.

Математика для Чайников №4 27 Июль 2019 18:03 #202

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Присутствует, но только в пределе.
Сам себе доктор наук

Математика для Чайников №4 27 Июль 2019 18:20 #203

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Sam Sebe wrote:
Присутствует, но только в пределе.

Это неверно
Каждому - своё.

Математика для Чайников №4 27 Июль 2019 18:31 #204

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Как неверно? Если xn+2 = xn+1 + xn, то

xn+2/xn+1 = 1 + 1/(xn+1/xn)

и в пределе Ф = 1 + 1/Ф независимо от x0 и x1, если доказать, что предел существует.
Сам себе доктор наук

Математика для Чайников №4 27 Июль 2019 18:58 #205

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Sam Sebe wrote:
Как неверно?

Неверно, что только в пределе
Каждому - своё.

Математика для Чайников №4 27 Июль 2019 22:58 #206

  • procrastinator
  • procrastinator's Avatar
Sam Sebe wrote:
Как неверно? Если xn+2 = xn+1 + xn, то

xn+2/xn+1 = 1 + 1/(xn+1/xn)

и в пределе Ф = 1 + 1/Ф независимо от x0 и x1, если доказать, что предел существует.
По всей видимости, Vladimirovich имеет в виду что
xn=c1Фn+c2(-1-Ф)n,
где константы c1 и c2 определяются первыми двумя членами последовательности.

Математика для Чайников №4 27 Июль 2019 23:46 #207

  • procrastinator
  • procrastinator's Avatar
procrastinator wrote:
xn=c1Фn+c2(-1-Ф)n
xn=c1Фn+c2(1-Ф)n, конечно.

Математика для Чайников №4 28 Июль 2019 04:05 #208

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Тогда бы уж выписали сразу и обе константы. Я такой формулы не встречал, хотя формулу Бине знаю, конечно. И сразу возникает вопрос, почему тогда формулой Бине называют не эту формулу, а ее частный случай?
Сам себе доктор наук

Математика для Чайников №4 28 Июль 2019 05:00 #209

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
Sam Sebe wrote:
Тогда бы уж выписали сразу и обе константы.
Да в том то и дело, что "константы" определяются начальными условиями
Здесь очень близкая идет аналогия с дифференциальными уравнениями, в данном случае
xn+2 = xn+1 + xn <=> x''=x'+x

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

Математика для Чайников №4 28 Июль 2019 05:20 #210

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Vladimirovich wrote:
Да в том то и дело, что "константы" определяются начальными условиями

Да никто и не сомневается, что константы не по начальным условиям, а по n. А вот выписать их, решив систему двух уравнений, не помешало бы, вдруг вся ожидаемая там громоздкость сильно упрощается.
Сам себе доктор наук
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум