В деревне Мартышкино у каждого мальчика все знакомые с ним девочки знакомы между собой. У каждой девочки среди её знакомых мальчиков больше, чем девочек. Докажите, что в Мартышкино мальчиков живёт не меньше, чем девочек.
Очень Можете любое свое доказательство, но кажется, здесь надо действовать по индукции, только не знаю индукцию по какой величине
Шаг базы: Для начала, рассмотрим самый простой случай, когда в Мартышкино есть только один мальчик и одна девочка. Ясно, что у девочки нет других знакомых мальчиков, так как их всего один. А у мальчика нет других знакомых девочек, так как их всего одна. Таким образом, количество мальчиков равно количеству девочек, что подтверждает наше утверждение.
Шаг индукции: Предположим, что для каждого n мальчиков в Мартышкино выполняется утверждение: количество мальчиков не меньше, чем количество девочек.
Теперь рассмотрим ситуацию, когда у нас есть (n+1) мальчик в деревне Мартышкино. Обозначим этого мальчика как М. Рассмотрим два случая:
1. У М связей с девочками больше, чем с мальчиками:
Пусть у М есть k девочек, с которыми он знаком, и m мальчиков, с которыми он знаком (k > m). Согласно условию, каждая девочка знакома со всеми девочками, которые знакомы с М, и каждая из этих девочек знакома с большим количеством мальчиков, чем девочек. Давайте посчитаем, сколько всего мальчиков и девочек может быть в этом случае:
- Количество девочек, знакомых с М, нам неизвестно, но мы знаем, что каждая из них знакома с большим количеством мальчиков (не меньше, чем девочек). Пусть каждая девочка, знакомая с М, знакома с l мальчиками. Тогда общее количество мальчиков, знакомых с М, будет равно k * l.
- Количество девочек, знакомых с М, плюс М, составляют все девочки в Мартышкино, то есть (k + 1) девочек.
- Количество мальчиков в Мартышкино теперь составляет m + k * l (мальчики, с которыми знаком М, и мальчики, с которыми знакомы девочки, знакомые с М).
По условию задачи у каждой девочки количество мальчиков, с которыми она знакома, больше, чем девочек. Пусть каждая девочка знакома с r мальчиками. Тогда она будет знакома (r + 1) мальчиками. Всего количество мальчиков, знакомых с девочками, будет равно k * (r + 1).
Таким образом, общее число мальчиков в Мартышкино (m + k * l) + k * (r + 1) = m + k * (r + l) + k.
Нам нужно показать, что общее число мальчиков в Мартышкино больше или равно общему числу девочек ((k + 1) + (k * (r + 1))). То есть:
(m + k * (r + l) + k) >= (k + 1) + (k * (r + 1))
Для доказательства этого неравенства, разложим обе его части:
m + k * (r + l) + k >= k + 1 + k * r + k
Упростим его:
m + k * (r + l) + k >= k * (r + 1) + 1 + k
После упрощения мы видим, что левая часть неравенства больше или равна правой части. Таким образом, утверждение верно в этом случае.
2. У М связей с мальчиками больше, чем с девочками:
Этот случай очень похож на предыдущий. Мы можем повернуть наше рассуждение и вместо мальчиков рассматривать девочек, а вместо девочек - мальчиков. Таким образом, мы можем прийти к выводу, что количество мальчиков не меньше, чем количество девочек, и в этом случае.
Таким образом, по индукции мы доказали, что в деревне Мартышкино мальчиков живет не меньше, чем девочек.