Олимпиадные задачи по теме «Комбинаторика» для 9 класса
В каждой клетке таблицы, состоящей из 10 столбцов и <i>n</i> строк, записана цифра. Известно, что для каждой строки <i>A</i> и любых двух столбцов найдётся строка, отличающаяся от <i>A</i> ровно в этих двух столбцах. Докажите, что <i>n</i> ≥ 512.
Расстоянием между числами <span style="text-decoration: overline;"><i>a</i><sub>1</sub><i>a</i><sub>2</sub><i>a</i><sub>3</sub><i>a</i><sub>4</sub><i>a</i><sub>5</sub></span> и <span style="text-decoration: overline;"><i>b</i><sub>1</sub><i>b</i><sub>2</sub><i>b</i><sub>3</sub><i>b</i><sub>4</sub><i>b</i><sub>5</sub></span> назовём максимальное <i>i</i>, для которого <i>a<sub>i</sub></i> ≠ <i>b<sub>i</sub></i>. Все пятизначные числа выписаны друг...
В стране <i>N</i> 1998 городов, и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из каждого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из каждого незакрытого города в любой другой, не делая пересадок в закрытых городах.