Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 14 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
kirilych |
|
|
Итак, моя задачка: Какое наибольшее число королей можно разместить на шахматной доске так, чтобы ни один король не бил более двух других? Пример с 33 королями строится довольно легко. То, что 34 не получится, вскоре становится ясно. Но строгого доказательства так и нашлось пока. В общем виде легко показать, что для любой четной доски можно поставить n^2/2 + 1 короля. Требуется доказать, что больше нельзя. Перепробовал всё и уже отчаялся. Выношу проблему сюда для любителей подобных задач. |
||
Вернуться к началу | ||
MihailM |
|
|
Интересная задача.
Я бы занялся всеми вариантами заполнения квадрата 4х4 девятью королями. В крайнем случае можно просто все тупо перебрать. По-моему там вариантов кот наплакал: 4х1, 2х1 и уголок в небольшом числе комбинаций. Гипотеза такая, что все эти варианты 9 королей сильно портят жизнь всем следующим квадратикам 4х4 и туда можно вставлять уже только по 8. |
||
Вернуться к началу | ||
kirilych |
|
|
Да, конечно, все такие гипотезы я уже рассмотрел. Но ни одна из них не хочет доходить до строгого доказательства, все остаются конструктивными соображениями, не более. Ни индукция, ни раскраска, ничего не получается... При этом максимальные расстановки действительно почти безвариантны, фактически всего два способа с небольшими вариациями для любой доски.
|
||
Вернуться к началу | ||
MihailM |
|
|
kirilych писал(а): Да, конечно, все такие гипотезы я уже рассмотрел Вы меня читали? Если вы знаете ВСЕ расстановки 9 королей на квадрате 4х4 - покажите их |
||
Вернуться к началу | ||
kirilych |
|
|
Собственно, принципиальных конструкций всего две (уже показанных для 8х8):
если не учитывать вращение "уголка". И да, конечно, обе конструкции "портят" клетки вокруг себя по периметру, поэтому ясно, что поместить их можно только в две противоположных четверти квадрата 8х8, а в оставшихся четвертях сумеем поставить намного меньше. Т.е. чисто конструктивно никаких сомнений, что 34 короля поставить нельзя. Как и в том, что в любой четной доске не поставишь более n^2/2 + 1. Проблема лишь в строгом доказательстве этого факта. |
||
Вернуться к началу | ||
MihailM |
|
|
kirilych писал(а): Собственно, принципиальных конструкций всего две Если это верно, то все доказано |
||
Вернуться к началу | ||
swan |
|
|
MihailM писал(а): Гипотеза такая, что все эти варианты 9 королей сильно портят жизнь всем следующим квадратикам 4х4 и туда можно вставлять уже только по 8. Наискосок не мешают |
||
Вернуться к началу | ||
MihailM |
|
|
swan писал(а): Наискосок не мешают По одному 4х4 идем. Ставим 8 королей в смежный, тогда все крайние полосы опять заняты (по другому вроде очевидно не получится). |
||
Вернуться к началу | ||
swan |
|
|
Тут тогда надо и все комбинации восьмерок рассматривать, чтобы это доказать. Сходу совсем не очевидно. Если это олимпиадная задача, то надеюсь у нее есть другое решение. Потому что такой путь, хоть и должен привести к доказательству, но как-то слишком громоздок.
|
||
Вернуться к началу | ||
MihailM |
|
|
swan писал(а): Тут тогда надо и все комбинации восьмерок рассматривать, чтобы это доказать Ну да. Вообще, если делать из нее задачу, брутфорс конечно желательно запустить на 8 и 9 королей на 4х4, к чему я ТС призывал. А то в таких задачах иногда какой-нибудь случай да ускользнет. |
||
Вернуться к началу | ||
На страницу 1, 2 След. | [ Сообщений: 14 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
На шахматной доске ладьи
в форуме Комбинаторика и Теория вероятностей |
2 |
296 |
14 мар 2019, 18:30 |
|
Ладьи на шахматной доске
в форуме Комбинаторика и Теория вероятностей |
11 |
583 |
12 мар 2019, 18:02 |
|
Инфекция на шахматной доске | 5 |
326 |
06 сен 2020, 07:16 |
|
Число путей ладьи из угла в угол на шахматной доске | 14 |
1480 |
29 апр 2018, 21:50 |
|
Вероятность вытащить короля и даму
в форуме Комбинаторика и Теория вероятностей |
3 |
802 |
12 мар 2015, 01:53 |
|
Вероятность вытащить даму и короля
в форуме Комбинаторика и Теория вероятностей |
5 |
618 |
11 мар 2015, 19:24 |
|
Проекция шахматной доски
в форуме Геометрия |
5 |
353 |
31 май 2018, 16:38 |
|
Задача про разбиение шахматной доски mXm | 1 |
383 |
23 янв 2015, 10:04 |
|
Три коня на доске
в форуме Размышления по поводу и без |
3 |
244 |
06 сен 2017, 10:22 |
|
17 чисел на доске
в форуме Размышления по поводу и без |
1 |
257 |
18 окт 2017, 15:57 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |