Sam Sebe wrote: Я нестрого выразился, прошу прощения.

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

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

en.m.wikipedia.org/wiki/Petersen_graph

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

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

Да, все уже просчитано до нас

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

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

Вот статья Акулича про симплекс-метод, для чайников - в самый раз, не заумь.
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

Еще одна олимпиадная задачка. Ей подошло бы хорошо известное название, потом догадаетесь какое.

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

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

Sam Sebe wrote: Я правильно понимаю, что а) "в точности по две клетки" относится к размеру домино, а не к способу покрытия и б) клетка доски считается покрытой если костяшка покрывает любую часть ее? Если так, то легко построить покрытие 9-ю костяшками и вряд-ли есть покрытие 8-ю.

procrastinator wrote: Программировал ли самоед это таким образом?

Название очевидно -

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

Решил посмотреть вспомогательную задачу, хоть пользы от нее оказалось мало.

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

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



Казалось бы, решение исходной задачи, будучи экстремальным, должно соответствовать тоже экстремальному случаю cnt < 17. Но, очевидно, это не так.

Ладно, поскольку задачку никто не решил, скажу ответ. Минимальное число костяшек равно 22. Остается уложить их - уловить! - на шахматной доске. Уловка-22. ))

Sam Sebe wrote: Ну для того, чтобы задачу решили ее нужно для начала задать. Я на 136% уверен, что решал не ту задачу, что Вы имели в виду. А что Вы имели в виду, я так и не понял.

Я вообще не считаю правильным, что тут задаются задачи, коих аффтар вообще не знает точного решения, а знает только rnd()
И не переношу их отсюда лишь из уважения к самоеду
Это никакая не математика.

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

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

procrastinator wrote:

1x2 wrote: Спасибо опять. Интересная статья, хотя явные очепятки на первой странице убивают желание ее читать.

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

Владимировичу отвечу чуть позже, чайку надо попить. ))

Тов. Владимирович, Вы уже не первый раз делаете такие замечания, тогда как надо было бы с самого начала, в первом же посте (как я всегда делаю), сформулировать, что такое математика для чайников и с чем ее едят. Например, так: Математика для чайников - это все что угодно, но заведомо не то, что подразумевает под математикой самоед. ))

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

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

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

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

Это и есть математика для чайников??

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

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

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

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

Мне в этой статье непонятно как ответ может быть d(n)=n³/3
Число полей растет, как n² и max доминошек тоже
А минимум растет как куб?

Vladimirovich wrote: Это очепятка аффтарoв.

ХайдукФан wrote: За такие очепятки надо на Соловки

XaйдукФан wrote:
Почему это хрень?

ХайдукФан wrote: Авторов, не авторов, но это индикатор того, что референты статью просто не читали. Поэтому и мне не очень хочется

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

Так мне и не удалось уловить пресловутые 22 костяшки методом Монте Карло. Не помогла даже такая стратегия ограничения случайности: если через одну от незанятой клетки оказывается занятая, то незанятую клетку между ними занимать, если можно, не нужно. Комбинации из 23 костяшек получаются, а из 22 никак.

Такие задачи обычно решаются методом динамического програмирования.