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

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

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
Sam Sebe wrote:
Да, верно, максимум = 10, но почему предел "физический", что это значит?
Я нестрого выразился, прошу прощения.

10 это чисто теоретический предел, далее которого решений не может быть в принципе.

А вот нет ли там дополнительных ограничений, надо считать.
Если нет, то это и ответ.
Каждому - своё.

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

  • $$$
  • $$$'s Avatar

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

  • procrastinator
  • procrastinator's Avatar
$$$ wrote: т.е. ребра графа - ничьи, а отсутствие ребра - результативная партия. Спасибо.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Да, исчерпывающее описание, но оно есть и на русском. У меня такой эрудиции и близко нет.
Сам себе доктор наук

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
Да, все уже просчитано до нас :)
Каждому - своё.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Vladimirovich wrote:
Да, все уже просчитано до нас :)

Мой товарищ даже закон соответствующий сформулировал, примерно такой: если ищешь что-то нужное, то ни за что не найдешь, а если чего-то достиг сам, то наверняка кто-то преуспел и до тебя. :)

А что касается этой задачи, то я попробовал получить требуемую матрицу n x n случайным перебором. При n < 9 матрицы возникают мгновенно. При n = 9 и, понятно, при n > 10 я ничего не дождался. А при n = 10 матрицы получаются не мгновенно, но довольно быстро. Вот первые 5 штук. Наверное, они отвечают одному и тому же графу, графу Петерсена. Посмотрите, а то, может, я ошибся, программируя.

Peter.png
Сам себе доктор наук
Last Edit: 13 Июль 2019 08:21 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Вот статья Акулича про симплекс-метод, для чайников - в самый раз, не заумь.
www.mathnet.ru/php/archive.phtml?wshow=p...d=11&option_lang=rus

Правда, Акулич этот ничем кроме задач для "Кванта" в математике не известен.
www.mathnet.ru/php/person.phtml?option_lang=rus&personid=115533

Но задачи эти очень хорошие, и из них даже целый сборник издан, который можно бесплатно скачать.
www.rulit.me/series/bibliotechka-kvant/k...ulki-get-553326.html
Сам себе доктор наук
Last Edit: 14 Июль 2019 18:17 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Еще одна олимпиадная задачка. Ей подошло бы хорошо известное название, потом догадаетесь какое.

Шахматная доска покрывается костяшками домино - в точности по две клетки - до тех пор, пока это возможно. По максимуму, понятно, потребуется 32 костяшки, а вот сколько нужно по минимуму?

Я попробовал найти решение на компьютере, просто перебирая все непокрытые клетки случайным образом и покрывая их в паре с любой (тоже случайной) соседней клеткой, если это возможно. Представляете, я проделал этот цикл 100 000 000 раз, но до минимума не добрался!
Сам себе доктор наук
Last Edit: 17 Июль 2019 08:18 by Sam Sebe.

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

  • procrastinator
  • procrastinator's Avatar
Sam Sebe wrote:
Еще одна олимпиадная задачка. Ей подошло бы хорошо известное название, потом догадаетесь какое.

Шахматная доска покрывается костяшками домино - в точности по две клетки - до тех пор, пока это возможно. По максимуму, понятно, потребуется 32 костяшки, а вот сколько нужно по минимуму?

Я попробовал найти решение на компьютере, просто перебирая все непокрытые клетки случайным образом и покрывая их в паре с любой (тоже случайной) соседней клеткой, если это возможно. Представляете, я проделал этот цикл 100 000 000 раз, но до минимума не добрался!
Я правильно понимаю, что а) "в точности по две клетки" относится к размеру домино, а не к способу покрытия и б) клетка доски считается покрытой если костяшка покрывает любую часть ее? Если так, то легко построить покрытие 9-ю костяшками и вряд-ли есть покрытие 8-ю.

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
procrastinator wrote:
клетка доски считается покрытой если костяшка покрывает любую часть ее?
Программировал ли самоед это таким образом? :glasses:
Каждому - своё.

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

  • procrastinator
  • procrastinator's Avatar
Название очевидно -
Warning: Spoiler! [ Click to expand ]

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Нет-нет, костяшка покрывает ровно две клетки целиком, сразу белую и черную, ни больше ни меньше. Не знаю, может, и похоже на тетрис, но есть название получше.
Сам себе доктор наук
Last Edit: 17 Июль 2019 17:28 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Решил посмотреть вспомогательную задачу, хоть пользы от нее оказалось мало.

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

Вот статистика 1 млн случайных экспериментов. Вверху изображена доска, на которой занято рекордно малое число клеток, cnt = 17 (плюсики). А наибольшее число занятых клеток, cnt = 32, отвечает тому много раз повторившемуся случаю, fre = 1750 раз, когда заняты все белые клетки или все черные.

million.png


Казалось бы, решение исходной задачи, будучи экстремальным, должно соответствовать тоже экстремальному случаю cnt < 17. Но, очевидно, это не так.
Сам себе доктор наук
Last Edit: 18 Июль 2019 05:49 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Ладно, поскольку задачку никто не решил, скажу ответ. Минимальное число костяшек равно 22. Остается уложить их - уловить! - на шахматной доске. Уловка-22. ))
Сам себе доктор наук
Last Edit: 19 Июль 2019 17:38 by Sam Sebe.

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

  • procrastinator
  • procrastinator's Avatar
Sam Sebe wrote:
Ладно, поскольку задачку никто не решил, скажу ответ. Минимальное число костяшек равно 22. Остается уложить их - уловить! - на шахматной доске. Уловка-22. ))
Ну для того, чтобы задачу решили ее нужно для начала задать. Я на 136% уверен, что решал не ту задачу, что Вы имели в виду. А что Вы имели в виду, я так и не понял.

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
Я вообще не считаю правильным, что тут задаются задачи, коих аффтар вообще не знает точного решения, а знает только rnd()
И не переношу их отсюда лишь из уважения к самоеду
Это никакая не математика.

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

Никто не мешает считать все, что угодно, но это не та тема.
Каждому - своё.

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

  • 1x2
  • 1x2's Avatar
procrastinator wrote:
Sam Sebe wrote:
Ну для того, чтобы задачу решили ее нужно для начала задать.
Видимо автор вопроса имел ввиду задачу о clumsy packing of dominoes
www.sciencedirect.com/science/article/pii/0012365X88900283
Как ее решать чайнику, не очень понятно. Может Хайдук может обьяснить?

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

  • procrastinator
  • procrastinator's Avatar
1x2 wrote:
procrastinator wrote:
Ну для того, чтобы задачу решили ее нужно для начала задать.
Видимо автор вопроса имел ввиду задачу о clumsy packing of dominoes
www.sciencedirect.com/science/article/pii/0012365X88900283
Как ее решать чайнику, не очень понятно. Может Хайдук может обьяснить?
Спасибо опять. Интересная статья, хотя явные очепятки на первой странице убивают желание ее читать.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
1x2 wrote:
procrastinator wrote:
Видимо автор вопроса имел ввиду задачу о clumsy packing of dominoes
www.sciencedirect.com/science/article/pii/0012365X88900283
Как ее решать чайнику, не очень понятно. Может Хайдук может обьяснить?

Да, получается, что это та задача. Но не в чрезмерной ее общности - не для любого n, не для треугольников и не для шестиугольников, а просто для шахматной доски. Так что она по силам и далеко не профессионалам. А что касается недопонимания, то тут, надо думать, сработал закон Мерфи. Это он виноват. ))

Владимировичу отвечу чуть позже, чайку надо попить. ))
Сам себе доктор наук
Last Edit: 20 Июль 2019 04:16 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Тов. Владимирович, Вы уже не первый раз делаете такие замечания, тогда как надо было бы с самого начала, в первом же посте (как я всегда делаю), сформулировать, что такое математика для чайников и с чем ее едят. Например, так: Математика для чайников - это все что угодно, но заведомо не то, что подразумевает под математикой самоед. ))

Не поленился, чтобы посмотреть первый пост этой, а также предыдущих веток.

"Мощный труд по популярному изложению гипотезы Римана о нулях дзета-функции
Многие вещи я даже не знал, например число Скьюза..."

"Математики из Принстона при помощи компьютерного моделирования смогли построить наиболее плотную упаковку тетраэдров в замкнутом трехмерном объеме из известных на сегодняшний день."

"Интересно, есть ли специалисты по этому вопросу?
Ищу pdf-ку (книгу или обзор) с красивыми задачками по внешнему произведению матриц и операциями с блоками ячеек"

Это и есть математика для чайников??
Сам себе доктор наук
Last Edit: 20 Июль 2019 04:40 by Sam Sebe.

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
Sam Sebe wrote:
Тов. Владимирович, Вы уже не первый раз делаете такие замечания, тогда как надо было бы с самого начала, в первом же посте (как я всегда делаю), сформулировать, что такое математика для чайников и с чем ее едят. Например, так: Математика для чайников - это все что угодно, но заведомо не то, что подразумевает под математикой самоед. ))

Не поленился, чтобы посмотреть первый пост этой, а также предыдущих веток.

"Мощный труд по популярному изложению гипотезы Римана о нулях дзета-функции
Многие вещи я даже не знал, например число Скьюза..."

Ну ведь там и не предлагалось решить гипотезу Римана :)
Просто для информации об интересной проблеме.

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

А программирование - это просто отдельная тема, вот и все
Каждому - своё.

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

  • XaйдукФан
  • XaйдукФан's Avatar
procrastinator wrote:
Спасибо опять. Интересная статья, хотя явные очепятки на первой странице убивают желание ее читать.
Согласен, читать эту хрень нет никакого желания. Предлагаю дождаться ув. Хайдука. Пусть объяснит, как он умеет, суть подхода. В конце концов должен же он хотя бы уметь читать на англицком?!.

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
Мне в этой статье непонятно как ответ может быть d(n)=n3/3
Число полей растет, как n2 и max доминошек тоже
А минимум растет как куб? :O
Каждому - своё.

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

  • ХайдукФан
  • ХайдукФан's Avatar
Vladimirovich wrote:
Мне в этой статье непонятно как ответ может быть d(n)=n3/3
Число полей растет, как n2 и max доминошек тоже
А минимум растет как куб? :O
Это очепятка аффтарoв.

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

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 81685
  • Thank you received: 1155
  • Karma: 82
ХайдукФан wrote:
Это очепятка аффтарoв.
За такие очепятки надо на Соловки :)
Каждому - своё.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
XaйдукФан wrote:
Согласен, читать эту хрень нет никакого желания.

Почему это хрень?
Сам себе доктор наук

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

  • procrastinator
  • procrastinator's Avatar
ХайдукФан wrote:
Vladimirovich wrote:
Мне в этой статье непонятно как ответ может быть d(n)=n3/3
Число полей растет, как n2 и max доминошек тоже
А минимум растет как куб? :O
Это очепятка аффтарoв.
Авторов, не авторов, но это индикатор того, что референты статью просто не читали. Поэтому и мне не очень хочется :)

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
procrastinator wrote:
Авторов, не авторов, но это индикатор того, что референты статью просто не читали. Поэтому и мне не очень хочется :)

Читать или не читать, а решение оттуда вырезать сюда надо. Оно-то ведь верное. Интересно (я тоже не читал)), оно единственное?

catch-22.png
Сам себе доктор наук
Last Edit: 20 Июль 2019 13:26 by Sam Sebe.

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

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 531
  • Thank you received: 7
  • Karma: 2
Так мне и не удалось уловить пресловутые 22 костяшки методом Монте Карло. Не помогла даже такая стратегия ограничения случайности: если через одну от незанятой клетки оказывается занятая, то незанятую клетку между ними занимать, если можно, не нужно. Комбинации из 23 костяшек получаются, а из 22 никак.
Сам себе доктор наук

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

  • ХайдукВикторович
  • ХайдукВикторович's Avatar
Такие задачи обычно решаются методом динамического програмирования.
Moderators: Grigoriy
Рейтинг@Mail.ru

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