Районная олимпиада, 2014-2015 учебный год, 11 класс

Сколькими способами можно выбрать 56 различных клеток на шахматной доске $8\times 8$ так, чтобы все черные клетки были выбраны, а в каждой строке и в каждом столбце было выбрано ровно по 7 клеток?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Задача эквивалентна выбору белых клеток из разных строк и столбцов. Пронумеруем строки от $1$ до $8$. В нечетных строках $4$ белые клетки находятся на одинаковых позициях. Всевозможных выборов белых клеток в этих четырех строках всего $4!$. Независимо от них количество всевозможных выборов четырех клеток не четных строках $4!$. Тогда всего выборов, удовлетворяющих условию задачи, $(4!)^2$.

Таңдалмайтын ақ шаршыны іріктеп алайық. Әрбір жолмен әрбір бағанда 4 ақ шаршы бар екені белгілі. Әрбір жолдан және әрбір бағаннан 1 ден артық ақ шаршы алып тасталынбайды.

1-ші жолда ақ түсті шаршыны алып тастау мүмкіндігі 4-ке тең. 2-ші жолдан алып тасталынатын ақ шаршы, 1-ші жолдан алып тасталған ақ шаршы бағанында болмауы керек. 2-ші жолда мұндай мүмкіндік саны–4.

3-ші жолда әртүрлі мүмкіндік саны 3 тең болады. Себебі 1-ші жолда алынған бір бағанға кеміді.

4-ші жолда әртүрлі мүмкіндік саны 3 тең болады. Себебі 2-ші жолда алынған бір бағанға кеміді.

5-ші жолда әртүрлі мүмкіндік саны 2 тең болады. Себебі 1-ші және 3-ші жолдардағы 2 бағанға кеміді.

6-шы жолда әртүрлі мүмкіндік саны 2 тең болады. Себебі 2-ші және 4-ші жолдардағы 2 бағанға кеміді.

7-ші жолда әртүрлі мүмкіндік саны 1 тең болады. Себебі 1-ші, 3-ші және 5-ші жолдардағы 3 бағанға кеміді.

8-ші жолда әртүрлі мүмкіндік саны 1 тең болады. Себебі 2-ші, 4-ші және 6-шы жолдардағы 3 бағанға кеміді.

Сонымен жалпы мүмкіндіктер саны 4∙4∙3∙3∙2∙2∙1∙1=576

Жауабы: 576