Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: 34 короля на шахматной доске
СообщениеДобавлено: 14 фев 2021, 21:12 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
14 фев 2021, 20:44
Сообщений: 56
Cпасибо сказано: 0
Спасибо получено:
18 раз в 17 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Прошу прощения, если по первости совершил ошибку с разделом. В описании раздела сказано "...задачи и проблемы, составленные Вами и не обязательно Вами, для которых Вы имеете решения", а раздела для "не имеете решения" рядом не обретается...

Итак, моя задачка:
Какое наибольшее число королей можно разместить на шахматной доске так, чтобы ни один король не бил более двух других?

Пример с 33 королями строится довольно легко. То, что 34 не получится, вскоре становится ясно. Но строгого доказательства так и нашлось пока.
В общем виде легко показать, что для любой четной доски можно поставить n^2/2 + 1 короля. Требуется доказать, что больше нельзя.
Перепробовал всё и уже отчаялся. Выношу проблему сюда для любителей подобных задач.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 14 фев 2021, 22:53 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
Интересная задача.
Я бы занялся всеми вариантами заполнения квадрата 4х4 девятью королями.
В крайнем случае можно просто все тупо перебрать.
По-моему там вариантов кот наплакал: 4х1, 2х1 и уголок в небольшом числе комбинаций.
Гипотеза такая, что все эти варианты 9 королей сильно портят жизнь всем следующим квадратикам 4х4 и туда можно вставлять уже только по 8.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 14 фев 2021, 23:13 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
14 фев 2021, 20:44
Сообщений: 56
Cпасибо сказано: 0
Спасибо получено:
18 раз в 17 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Да, конечно, все такие гипотезы я уже рассмотрел. Но ни одна из них не хочет доходить до строгого доказательства, все остаются конструктивными соображениями, не более. Ни индукция, ни раскраска, ничего не получается... При этом максимальные расстановки действительно почти безвариантны, фактически всего два способа с небольшими вариациями для любой доски.
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 14 фев 2021, 23:27 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
kirilych писал(а):
Да, конечно, все такие гипотезы я уже рассмотрел

Вы меня читали? Если вы знаете ВСЕ расстановки 9 королей на квадрате 4х4 - покажите их

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 14 фев 2021, 23:39 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
14 фев 2021, 20:44
Сообщений: 56
Cпасибо сказано: 0
Спасибо получено:
18 раз в 17 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Собственно, принципиальных конструкций всего две (уже показанных для 8х8):
Изображение
если не учитывать вращение "уголка".
И да, конечно, обе конструкции "портят" клетки вокруг себя по периметру, поэтому ясно, что поместить их можно только в две противоположных четверти квадрата 8х8, а в оставшихся четвертях сумеем поставить намного меньше. Т.е. чисто конструктивно никаких сомнений, что 34 короля поставить нельзя. Как и в том, что в любой четной доске не поставишь более n^2/2 + 1.
Проблема лишь в строгом доказательстве этого факта.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 15 фев 2021, 01:03 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
kirilych писал(а):
Собственно, принципиальных конструкций всего две

Если это верно, то все доказано

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 15 фев 2021, 07:34 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
MihailM писал(а):
Гипотеза такая, что все эти варианты 9 королей сильно портят жизнь всем следующим квадратикам 4х4 и туда можно вставлять уже только по 8.

Наискосок не мешают

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 15 фев 2021, 10:27 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Наискосок не мешают

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 15 фев 2021, 11:07 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Тут тогда надо и все комбинации восьмерок рассматривать, чтобы это доказать. Сходу совсем не очевидно. Если это олимпиадная задача, то надеюсь у нее есть другое решение. Потому что такой путь, хоть и должен привести к доказательству, но как-то слишком громоздок.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: 34 короля на шахматной доске
СообщениеДобавлено: 15 фев 2021, 11:32 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Тут тогда надо и все комбинации восьмерок рассматривать, чтобы это доказать

Ну да. Вообще, если делать из нее задачу, брутфорс конечно желательно запустить на 8 и 9 королей на 4х4, к чему я ТС призывал. А то в таких задачах иногда какой-нибудь случай да ускользнет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 14 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
На шахматной доске ладьи

в форуме Комбинаторика и Теория вероятностей

gfibr

2

296

14 мар 2019, 18:30

Ладьи на шахматной доске

в форуме Комбинаторика и Теория вероятностей

gfibr

11

583

12 мар 2019, 18:02

Инфекция на шахматной доске

в форуме Задачи со школьных и студенческих олимпиад

anton-petrunin

5

326

06 сен 2020, 07:16

Число путей ладьи из угла в угол на шахматной доске

в форуме Дискретная математика, Теория множеств и Логика

K1b0rg

14

1480

29 апр 2018, 21:50

Вероятность вытащить короля и даму

в форуме Комбинаторика и Теория вероятностей

gagat

3

802

12 мар 2015, 01:53

Вероятность вытащить даму и короля

в форуме Комбинаторика и Теория вероятностей

gagat

5

618

11 мар 2015, 19:24

Проекция шахматной доски

в форуме Геометрия

Rassamaha78

5

353

31 май 2018, 16:38

Задача про разбиение шахматной доски mXm

в форуме Дискретная математика, Теория множеств и Логика

Nikolay Moskvitin

1

383

23 янв 2015, 10:04

Три коня на доске

в форуме Размышления по поводу и без

Xenia1996

3

244

06 сен 2017, 10:22

17 чисел на доске

в форуме Размышления по поводу и без

Xenia1996

1

257

18 окт 2017, 15:57


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved