- IV Интернет-олимпиада по математике/XIV тур Математического Марафона (12)→
- XV тур математического марафона (12)→
- Вторая открытая Интернет-олимпиада по математике (9)→
- Третья Интернет-олимпиада по математике/XIII тур Математического Марафона (12)→
- Задачи конкурса Ponder This компании IBM: 7↓
- Задачи областной олимпиады по математике 2010 (5)→
- Первая открытая Интернет-олимпиада по математике (9)→
- Задачи областной олимпиады по математике 2009 (5)→
- Как доказывать олимпиадные неравенства
- Задачи международного турнира
- XXI тур Математического Марафона
- Отбор на XVI Всеукраинский турнир - Часть 2
- Отбор на XVI Всеукраинский турнир - Часть 1
- Далеко, далеко, на лугу пасутся ко...
- Людоед и гномики
- Поиск фальшивой монеты
- Два парома
- Как вычислять бесконечные суммы: часть 1
- Вариации на тему игры Баше
- Мотоциклист, велосипедист и пешеход
- Утроение числа после перестановки цифр
- Как вычислять бесконечные суммы: часть 2
- Задача о поиске радиоактивных шаров
- Нестандартное решение задачи по теории вероятности
- Математические маневры
- Задача о двух мудрецах
- Ранжирование грузов по весу
Задача
Широко известна задача расположения восьми ферзей на шахматной доске так, чтобы они не угрожали друг другу. Один из вариантов её решения представлен ниже:
Ф | |||||||
Ф | |||||||
Ф | |||||||
Ф | |||||||
Ф | |||||||
Ф | |||||||
Ф | |||||||
Ф |
Для решения же конкурсной задачи от IBM необходимо найти, какое наибольшее количество ферзей можно разместить на доске NxN так, чтобы каждый был под боем не более чем у одного ферзя. Требуется обосновать свой результат и найти требуемые расположения для досок 8х8 и 30х30. Решения должны представлять собой пары координат (х,у).
Решение
Докажем, что верхняя граница для доски NxN равна 4N/3. Поскольку каждый ферзь угрожает не более чем одному другому ферзю, то не может быть больше двух ферзей на горизонталь/вертикаль.
Обозначим через количество горизонталей с i ферзями, а – количество вертикалей с i ферзями.
Понятно, и таким образом . Так же и для y: .
Каждый из ферзей в горизонталях уже угрожает ферзю, так что как минимум в вертикалях стоит только по одному ферзю, т.е. . Аналогично .
Количество ферзей m равно а также . Решая простое неравенство получим:
Задайте вопрос на блоге о математике