Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Комбинаторика!
Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга и стояли симметрично относительно диагонали, проходящей через нижнее левое угловое поле?
11111110 11111101 11111011 11110111 11101111 11011111 10111111 01111111 Где 0 диагональ, на которой нельзя размещать ладьи, если я правильно понял условие. Штудирование учебников привело меня к этому: (1+x)^8 - ладийный полином для запрещённой области, состоящей из 0. Его разложение это x^8+8 x^7+28 x^6+56 x^5+70 x^4+56 x^3+28 x^2+8 x+1 Размещения это = 8! - r1(A)*7!+r2(A)*6!-r3(A)*5!+r4(A)*4!-r5(A)*3!+r6(A)*2!-r7(A)+r8(A) Где A - запрещённая область нашей доски (0) 8! - количество размещений на нашей доске 8 ладей. 8!-8*7!+28*6!-56*5!+70*4!-56*5!+70*4!-56*3!+28*2!-8+1 Здесь ответом является 9793, но это просто количество способов размещения ладей на области состоящей из единичек (1), а как учесть то, что у меня 8 ладей, фиг знает! 9793 нормально, но когда как учесть симметрию и количество ладей? Отредактировано Ranger21, 14.03.2010 в 15:01. |
14.03.2010, 14:56 | #1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Очевидно, что из макс возможного кол-ва размещений (8!) нужно вычесть "плохие случаи", когда ладьи стоят не симметрично. |
14.03.2010, 17:16 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Хмм, а как эти плохие случаи сосчитать без тупого перебора?
Их много... Ranger21 добавил: И у меня голова начинает болеть, когда я их в мозгу пытаюсь перебрать... |
14.03.2010, 20:36 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Ranger21, предлагаю выбрать методом научного тыка. Это либо сочетания, либо повторения, либо размещения. |
14.03.2010, 20:39 | #4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Hellfim, С из 56 по 8 ? Ой не... тогда это много выйдет...
Либо какой-нибудь 8!/4!*4! Научный тык, потому что ты не знаешь как точно, или это подсказка мне?) |
14.03.2010, 20:54 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Потому что не знаю это раз.
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Почему ты считаешь, что так разместить нельзя? =) Они симметричны относительно этой диагонали. |
14.03.2010, 22:31 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ZLOBICH
Kicked by XimikS
offline
Опыт:
4,727Активность: |
К.О. говорит что задача на логику, и не решается комбинаторикой ранневузовского уровня. Ответ вроде 3 :dunno: |
14.03.2010, 22:47 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
К.О. сообщает, что есть больше трех вариантов и это даже если не учитывать что ладьи можно по-разному разместить.
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 |
14.03.2010, 23:31 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ZLOBICH
Kicked by XimikS
offline
Опыт:
4,727Активность: |
Hellfim, Теперь у нас есть 7 вариантов на двоих! |
14.03.2010, 23:34 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Вы условие задачи читали?
Hellfim, Это не есть симметрия относительно диагонали, проходящей через нижнее левое угловое поле. ZLOBICH, Ну вообще задача 4ая из 10ти, поэтому уровень должен быть ниже. В другом варианте у другого человека размещение 8 ферзей на доске, там 92 способа по википедии, причём везде написано, что не существует формулы для вычисления этих способов. |
14.03.2010, 23:55 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Ranger21, проведи линию симметрии по этой диагонали и... УДИВИСЬ! |
15.03.2010, 00:08 | #11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
То есть ты хочешь сказать, что размещение на самой диагонали есть симметрия относительно диагонали?)
Тогда это значительно упрощает (наверно) задачу. |
15.03.2010, 00:10 | #12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Ranger21, ну проведи прямую, каждая ладья отражается сама в себя. Во всяком случае в математике это так... |
15.03.2010, 00:37 | #13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Что-то мне ничего не удаётся, слишком сложная задача для моих мозгов. (
А вот такая задача.... 1. 15 школьников строят для прогулки в 5 рядов по 3 человека в ряду. Сколько раз можно это сделать так, чтобы никакие 2 школьника не оказались дважды рядом? Не понимаю условие |
15.03.2010, 17:42 | #14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Hellfim
Новичок
offline
Опыт:
79,700Активность: |
Ranger21, размещение (А), гогого. Эта задача из темы "Расставить по полочке n книг так, чтоб A и B стояли рядом". |
15.03.2010, 19:01 | #15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Ranger21
I love beatiul days XD
offline
Опыт:
13,274Активность: |
Hellfim, Блин... точняк.... из общих размещений вычесть те, когда они рядом стоят.
Эх, спасибо! Пойду считать Ranger21 добавил: Ага, только у нас 5 полочек! И варианты очень опасные.... опасные! Ranger21 добавил: Ага, только у нас 5 полочек! И варианты очень опасные.... опасные! |
15.03.2010, 22:25 | #16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|