Комбинаторика шахматных коней

[Xenia1996]

Сколькими способами можно расставить на шахматной доске, размером

а) $5\times 5$

б) $7\times 7$

в) $(2n+1)\times (2n+1)$ (n - натуральное число)


максимальное (для доски этого размера) число коней таким образом, чтобы ни один из расставленных коней не угрожал ни одному из остальных (все кони абсолютно идентичны)?

[MrDindows]

Случайно не одним?:)

[Xenia1996]

MrDindows в сообщении #434889 писал(а):

Случайно не одним?:)

Что, снова в угадалки будем играть? Это мне проблему $P=NP$ напоминает

[ИСН]

C конями-то просто: их ставят на все чёрные поля.

[Xenia1996]

ИСН в сообщении #434900 писал(а):

C конями-то просто: их ставят на все чёрные поля.

Вы хотели сказать "белые"?

[MrDindows]

Xenia1996 в сообщении #434905 писал(а):

ИСН в сообщении #434900 писал(а):

C конями-то просто: их ставят на все чёрные поля.

Вы хотели сказать "белые"?

На те, которых больше=)

[Xenia1996]

MrDindows в сообщении #434912 писал(а):

На те, которых больше=)

(Оффтоп)

Когда я в 4 года научилась играть в шахматы, мне объяснили правило "Light on Right".

-- Чт апр 14, 2011 22:39:10 --

ИСН в сообщении #434900 писал(а):

C конями-то просто: их ставят на все чёрные поля.

Я так понимаю, доказательство максимальности числа коней и единственности расстановки всем, кроме меня, кажется очевидным. Что ж, пусть будет так.

[MrDindows]

Я его просто не знаю...)

[Xenia1996]

MrDindows в сообщении #434927 писал(а):

Я его просто не знаю...)

Могу показать на примере доски $3\times 3$.
Разбейте всю доску на 5 непустых непересекающихся подмножеств:

(a1, b3),(a2, c1), (a3, c2), (b1, c3), (b2).

Предположим, что коней не менее шести. Тогда, по Дирихле, найдутся два коня в одном из этих пяти подмножеств. В подмножестве (b2) они быть не могут, а в любом другом они бьют друг друга.

Надеюсь, как доказать единственность расстановки Вы сами поняли?
Если нет, объясню.

[age]

ИСН в сообщении #434900 писал(а):

C конями-то просто: их ставят на все чёрные поля.

А как насчёт ферзей. Помню я формулировал аналогичную задачу, но никто так и не ответил.
Уточнение: ферзи берутся 2 цветов, в случае нечётного количества белых на 1 больше чем чёрных.

-- Пт апр 15, 2011 00:28:39 --

Да ещё, а как изменится задача про коней, если коней также брать 2 цветов?

[Xenia1996]

age в сообщении #434951 писал(а):

ИСН в сообщении #434900 писал(а):

C конями-то просто: их ставят на все чёрные поля.

А как насчёт ферзей. Помню я формулировал аналогичную задачу, но никто так и не ответил.
Уточнение: ферзи берутся 2 цветов, в случае нечётного количества белых на 1 больше чем чёрных.

-- Пт апр 15, 2011 00:28:39 --

Да ещё, а как изменится задача про коней, если коней также брать 2 цветов?

Можно ещё и о Магараджах вспомнить
И вот тут.

[age]

Xenia1996
Чёрные и белые или одного цвета?

[Xenia1996]

age в сообщении #434958 писал(а):

Xenia1996
Чёрные и белые или одного цвета?

По ссылке про одноцветные говорится. У Вас, я вижу, два цвета.

[Xenia1996]

Доказательство единственности расстановки на примере доски $5\times 5$.
Разбейте всю доску на 13 непустых непересекающихся подмножеств:

1. (a1, b3)
2. (a2, b4)
3. (a3, c2)
4. (a4, c3)
5. (a5, c4)
6. (b1, d2)
7. (b2, d1)
8. (b5, d4)
9. (c1, e2)
10. (c5, e4)
11. (d3, e5)
12. (d5, e3)
13. (e1)

Теперь мы видим, что в клетке e1 должен стоять конь, в противном случае имеем 13 коней в 12 оставшихся подмножествах и тогда, по Дирихле, какие-то два бьют друг друга.

Теперь рассмотрим подмножество (d3, e5). Конь не может стоять на d3, ибо тогда он будет бить коня на e1 (а то, что на e1 конь есть, мы уже доказали). Но если конь не стоит на d3, он обязан стоять на e5, в противном случае в подмножестве (d3, e5) не будет ни одного коня и тогда у нас снова будет 13 коней в 12 подмножествах.

Итак, мы доказали, что на e1 и на e5 стоят кони.
Рассматривая множество (a5, c4), мы таким же образом доказываем существование коня на a5.

Аналогично доказывается, что оставшиеся 10 коней стоят на оставшихся белых клетках (при допущении, что клетка e1 - белая).