МАЛЫЙ МЕХМАТ МГУ

Листок 2.  Комбинаторика

1.  

В школьной столовой 5 кранов для умывания. Каждый может быть закрыт или открыт. Сколькими способами может течь вода в столовой?
 

2.  

Некое современное здание имеет форму куба, стоящего на четырёх колоннах. Имеется 6 красок. Сколькими способами можно покрасить грани здания этими красками в 6 цветов? (Каждая грань красится целиком в один цвет, разные грани красятся в разные цвета.)
 

3.  

а) В заборе 20 досок, каждую надо покрасить в синий, зелёный или жёлтый цвет, причём соседние доски красятся в разные цвета. Сколькими способами это можно сделать?
б) А если требуется ещё, чтобы хоть одна из досок обязательно была синей?
 

4.  

а) Сколько можно составить различных (не обязательно осмысленных) слов из k букв, используя русский алфавит?
б) А если потребовать, чтобы буквы в словах не повторялись?
в) Сколькими способами можно переставить буквы в слове из k различных букв?
 

5.  

а) Сколько существует 10-значных чисел, не содержащих цифру 1?
б) Сколько из них содержит цифру 9 (хотя бы одну)?
 

6.  

а) Десять девушек водят хоровод. Сколькими способами они могут встать в круг? б) Сколько ожерелий можно составить из 10 различных бусин? в)* А если в ожерелье всего 3 белых и 7 синих бусин?
 

7.  

а) Сколько строк можно составить из 0 и 1, чтобы в каждой строке было 10 цифр?
б) На дереве растут 10 яблок. Сколькими способами можно сорвать несколько из них?
 

8.  

Меню в школьном буфете постоянно и состоит из n разных блюд. Петя хочет каждый день выбирать себе завтрак по-новому (за раз он может съесть от 0 до n разных блюд).
а) Сколько дней ему удастся это делать?
б) Сколько блюд он съест за это время?
в) Вася решил последовать примеру Пети, но съедать каждый день нечетное число блюд. Сколько дней ему удастся это делать?
г) Сколько блюд он съест за это время?
 

9.  

а) Сколькими способами можно расставить на шахматной доске 8 различных ладей так, чтобы они не били друг друга?
б) Ответом в предыдущем пункте является квадрат некоторого числа. Объясните это явление.
 

10.  

Сколькими способами можно расставить на шахматной доске 8 неразличимых ладей так, чтобы они не били друг друга?
 

11.  

Фабрика игрушек выпускает разноцветные кубики. У всякого кубика каждая грань окрашена целиком одной из шести красок, имеющихся на фабрике, причём разные грани одного кубика окрашены разными красками. Сколько видов кубиков выпускает фабрика?
 

12*.  

Фабрика из предыдущей задачи начала выпуск параллелепипедов 1×1×2, склеивая по два из выпускаемых ею кубиков. Сколько получится различных видов новой игрушки?
 

13*.  

Решите две предыдущие задачи, заменив куб на тетраэдр (и 6 цветов на 4).
 

14.  

а) Какое наибольшее число неразличимых слонов можно расставить на шахматной доске так, чтобы они не били друг друга?
б) Докажите, что число способов такой расстановки — квадрат некоторого числа.
в)* Найдите это число. (Сначала решите такую же задачу для досок 2×2, 3×3, 4×4, ...)
 

15.  

Сколько существует строк из 20 цифр, в которых встречаются только нули и единицы, причём никакие два нуля не стоят рядом?
 

16*.  

В таблицу размера k×l записывают числа +1 и -1 так, чтобы произведение чисел в каждой строке и в каждом столбце равнялось 1. Сколькими способами это можно сделать?



Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS