Форум умных людей

Это задачка из мат. конкурса Harvard-MIT Mathematics Tournament (HMMT)

На шахматной доске 20х20 клеток нужно разместить максимальное количество ферзей так, чтобы каждый ферзь находился под ударом не более 1 раза.
Напомню, ферзь ходит по горизонтали, вертикали и диагонали шахматной доски, не зависимо от количества клеток, ее составляющей.

При этом, подсчет очков за решение задачи на конкурсе производится следующим образом: за 20 размещенных согласно условию ферзей начисляется 0 балловв, за каждый последующий выставленный ферзь начисляется 5 баллов. Предполагается, что на данном вопросе можно заработать 25 баллов.

Знаю, что можно больше 20 и знаю как, но к 25 и близко не подошел.
Приглашаю поучаствовать всех заинтересовавшихся.

поставил 24

24 и у меня уже получилось.
пока никто не доказал (во всяком случае, мне это неизвестно), что можно 25, и что нельзя больше, чем 25.

Ну нашел я решение для 25. И на что я эти баллы смогу обменять? ))

Ваши баллы (решение) Вы можете обменять на местную валюту - "спасибку" от меня ))
кстати, как полагаете, возможно ли "продолжение банкета"?

(http://i25.fastpic.ru/big/2012/1031/d9/b27fbb6669c014d0baf32b26399df0d9.png) (http://fastpic.ru/)

Кстати я или нашёл решение для 26 или доказал что больше 25 не существует.

Вы "или" нашли решение для 25 ))
док-ва невозможности 26 я не увидел, разве только косвенно невозможность поставить еще одного ферзя в предложенном Вами раскладе. однако, расклады ведь могут быть иными ;)

не догоняю как ставить - просто подбором чтоли, или можно чё-то порешать???

а хз!?
я потому и задал в "помогите решить"

То что я написал к этому рисунку отношения не имеет. У меня или есть другой рисунок с 26 ферьзями или доказательство того что 26 расставить нельзя. Попробуйте угадать что именно. 

Кажется ,у тебя есть доказательство,что 25-это предел!!!!!!!!!

Простое доказательство, что не может быть больше 26!
 Показать скрытый текст
 Над 25  :think:

Проще сказать что на квадрате 3x3 можно поставить 4 ладьи, следовательно на квадрате 20x20 можно поставить 6*4+2=26 ладей и поэтому не более 26 ферзей.

не согласен. На квадрате 2х2 можно поставить 2 ладьи, тогда на квадрате 20х20 можно поставить 10*2= не более 20-ти ладьей

так 26 - можно?  ???

зы: покажите  :nyam:

26
Показать скрытый текст

вроде всё верно, браво. а 27?

уже доказали что 26 это максимум.

да ладно! точно? блин, вот я просмотрел!%())(*?:;;:?*:%;№%  :o ну ладно, можно ссылочку на доказательство?

http://nazva.net/forum/index.php/topic,8371.0.html

Алгоритм решения можно?

Вы даете ссылку на тему в целом. А толкуете о доказательстве.

куда же Вы смотрите


(http://i46.fastpic.ru/big/2012/1105/70/ee140f7675441e361d1298e049e1c270.png) (http://fastpic.ru/)


по другому.
решаем эту задачу для ладей. пусть число горизонтальных пар 7. перестановкой вертикалей и горизонталей размещаем все эти ладьи в верхнем левом прямоугольнике 7х14. в правом нижнем размером 13х6 можно разместить 6 вертикальных пар. если мы хотим добавить ещё одну горизонтальную пару то придётся убрать 2 вертикальные, т.е. общее число ладей уменьшится. ещё вариант 6 горизонтальных, 6 вертикальных пар и 2 одиночные ладьи - то же самое число 26.

как расставлял?

Расставляла программа-стандартная программа перебора вариантов. Таким образом довольно быстро можно расставить 25 ферзей. А вот чтобы получить первое решение для 26 ждать пришлось бы может быть месяц или 10000 лет. После некоторой оптимизации программа стала работать во много раз быстрее и нашла решение для 26 даже быстрее чем раньше для 25. Но как  выяснилось это из-за того что в новом варианте была ошибка и большинство расстановок программа пропускала без проверки.

А еще такая формула есть для доски n x n - [4n/3]. Для доски 20 х 20 получается [80/3]=26.