В стране есть 20 городов, которые соединены между собой 172 авиалиниями. Предположим, что между двумя городами есть только одна авиалиния. Докажите, что из любого города можно попасть в любой город, возможно, с пересадками.

Доказательство

Докажем от противного.

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

Рис. 7. Иллюстрация к задаче

Следовательно, отсутствует авиалиния и еще 18 авиалиний, которые связывают другие города либо с городом , либо с городом , то есть всего отсутствует 19 авиалиний.

В стране 20 городов, следовательно, всего теоретически возможно провести авиалиний.

Тогда если из 190 возможных авиалиний 19 отсутствуют, то присутствует всего:

авиалиния

Однако это противоречит условию:

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

Пример

Задача 7

Дано слово «логарифм». Сколько существует способов поменять местами буквы в этом слове так, чтобы в полученном буквосочетании согласные были упорядочены по алфавиту слева направо?

Решение

Например, нам подойдут следующие буквосочетания: ОАИГЛМРФ или ГОАЛИМРФ, или ГЛМАИРОФ. В каждом буквосочетании согласные идут в определенном порядке по алфавиту (ГЛМРФ), следовательно, общее количество вариантов таких буквосочетаний определяется только 3 гласными. Поэтому достаточно определить 3 места из 8 для гласных, после чего все буквы расставляются однозначно. А это будет способов.

Ответ: 336 способов.

Список литературы

1. Мордкович А.Г. Алгебра и начала математического анализа 10-11 кл. В. 2 ч. Ч. 1: Учебник для общеобразоват. учреждений. – М.: Мнемозина, 2009.

2. Муравин Г.К., Муравина О.В. Алгебра и начала математического анализа. – М.: Дрофа.

3. М.И. Шабунин, А.А. Прокофьев, Т.А. Олейник, Т.В. Соколова. Алгебра. Начала математического анализа. Профильный уровень: задачник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2009.

4. Мордкович А.Г. Алгебра и начала анализа 10-11 кл. В. 2 ч. Ч. 2: Задачник для общеобразоват. учреждений. – М.: Мнемозина, 2009.

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Интернет-сайт «Математический тандем» (Источник)

2. Интернет-сайт YouTube (Источник)

3. Интернет-сайт «МатБюро» (Источник)

Домашнее задание

1. Глава 20, задания 56, 67, 82 (стр. 382–386) – М.И. Шабунин, А.А. Прокофьев, Т.А. Олейник, Т.В. Соколова. Алгебра. Начала математического анализа. (Источник).

2. У Васи дома живут 4 кота.

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

3. Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

4. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать двух человек одного пола?