Question

Назовем человека малообщительным, если у него менее 10 знакомых. Назовем человека чудаком, если все знакомые у него малообщительны. Докажите, что количество чудаков не больше количества малообщительных

Answer 1

9. У 10 малообщительных 10 друзей, их друзья это чудаки => их поровну Этот вариант наихудший тк среди малообщительных нет взаимознакомств, значит наибольшее кол во чудаков, Если среди 10 малообщительных есть хотя бы одно взаимознакомство, то Судаков будет 8 => если есть взаимные знакомства то малообщительных по любому больше чудаков, сам только что решал

Answer 2

Давайте докажем это утверждение методом математической индукции.

Пусть N - это количество людей в группе. Для начала рассмотрим базовый случай:

1. Если N = 1, то у этого человека не может быть ни знакомых, ни малообщительных друзей. Таким образом, количество чудаков (0) не больше количества малообщительных (0).

Теперь давайте предположим, что утверждение верно для некоторого числа людей k и докажем его для k+1 человека:

Пусть есть k+1 человек в группе. Рассмотрим две ситуации:

1. Если у последнего, k+1-го человека есть более 10 знакомых, то он не считается малообщительным. Поскольку все остальные (первые k человек) считаются малообщительными, то у него не может быть других малообщительных друзей. Таким образом, количество чудаков в группе из k+1 человека равно количеству чудаков в группе из k человек.

2. Если у последнего, k+1-го человека есть менее 10 знакомых, то он считается малообщительным. Теперь у него есть k других малообщительных друзей (первые k человек). Таким образом, количество чудаков в группе из k+1 человека равно k (из малообщительных первых k человек) плюс 1 (последний человек). То есть, количество чудаков в группе из k+1 человека равно k+1.

Таким образом, мы доказали, что если утверждение верно для k человек, то оно верно и для k+1 человека. Мы уже убедились, что оно верно для N=1. Следовательно, оно верно для любого N.

Таким образом, количество чудаков в группе никогда не превысит количество малообщительных.