4:4 задача, спасибо большое

+ 0 -

Prostaya17

19 марта 2014 г., 12:08:14 (10 лет назад)

Из описания задачи следует что у Винни Пуха как минимум 5 друзей. И "5 друзей" очевидно удовлетворяет условию, а значит является частью ответа.
Посмотрим может ли быть у Винни Пуха 6 друзей. Пусть четверо из них живут на расстоянии 2км от дома Винни Пуха и двое на расстоянии 5км. Очевидно, что как бы мы ни выбирали 5 из этих 6 друзей, среди них всегда найдется четверка, удовлетворяющая условию. Т.е. "6 друзей" тоже является частью ответа.
Посмотрим может ли друзей быть больше. Рассмотрим вариант 7 друзей.
Чтобы доказать, что 7 друзей быть не может, нужно показать что из этих 7 друзей, всегда найдется такая пятерка, что любая четверка, входящая в эту пятерку, не будет удовлетворять условию. Для наглядности представим 7 друзей числами, соответствующими тому на каком расстоянии от дома Винни Пуха они живут.
2225xyz - 7 друзей, x, y, z - какие-то числа. Рассмотрим сначала вариант, когда x,y,z это числа не равные 2 и не равные 5, например 6,7,8:
2225678 - придумаем теперь из этих семи друзей пятерку такую, что любая входящая в нее четверка не будет удовлетворять условию. Пусть 67822.
Теперь рассмотрим еще 4 варианта: когда числа xyz это 222,555,225,552
1) 2225222 - придумаем теперь из этих семи друзей пятерку такую, что любая входящая в нее четверка не будет удовлетворять условию. Пусть 22222.
2) 2225555 - придумаем теперь из этих семи друзей пятерку такую, что любая входящая в нее четверка не будет удовлетворять условию. Пусть 55552.
3) 2225225 - придумаем теперь из этих семи друзей пятерку такую, что любая входящая в нее четверка не будет удовлетворять условию. Пусть 22222.
4) 2225552 - придумаем теперь из этих семи друзей пятерку такую, что любая входящая в нее четверка не будет удовлетворять условию. Пусть 55522.
Таким образом мы показали что на каком бы расстоянии ни жили 7 друзей Винни Пуха, всегда найдется пятерка не удовлетворяющая условию. А значит 7 друзей быть не может.
А значит не может быть и больше чем 7 друзей, ведь мы всегда сможем найти такие же неподходящие пятерки как для варианта 7 друзей.
Итого ответ будет: 5 или 6 друзей.