Лемма (Холл). Пусть есть k мальчиков и некоторое количество девочек, при этом любая группа из m мальчиков знает не менее, чем m девочек (считаем, что группа знает девочку, если это девочку знает хотя бы один мальчик из группы). Тогда каждому мальчику можно найти невесту среди знакомых ему девочек так, чтобы любая девочка была невестой не более, чем одного мальчика. Доказательство. Пусть еще не все мальчики - женихи, на первом шаге выберем любого мальчика без невесты, а он пригласит всех девочек, с которыми он знаком. На каждом последующем шаге будем добавлять в рассмотрение женихов всех выбранных девочек, а они тоже пригласят всех девочек, с которыми они знакомы. Тогда: 1. На каком-то шаге мы выберем девочку без жениха (всякий раз, если в группе есть m мальчиков, будет не менее m девочек. Если всё время у всех девочек будут женихи, то равно или поздно в группе будут все k мальчиков и, соответственно, не менее k девочек. Ну а поскольку невест не больше k - 1, то хотя бы у одной не будет жениха). 2. Найдя девочку без жениха, поженим её с тем, кто её пригласил. Оставшуюся без пары девочку поженим с тем, кто пригласил её, и так далее. В конце концов мальчик, изначально не умевший пары, получит невесту, а все мальчики - женихи, останутся женихами. Повторяя подобные операции можно найти всем мальчикам пару.
А теперь к задаче ;) Пусть 100-элементные подмножества - мальчики, 101-элементные подмножества - девочки. Будем говорить, что мальчик знает девочку, если они отличаются на один элемент (например, {1, 2, ..., 100} знает {1, 2, ..., 101}). Заметим, что любые m мальчиков суммарно знают не менее m девочек: каждый знает 1916 девочек, а общих знакомых девочек, посчитанных дважды, на каждого не больше 101. Тогда по лемме каждому мальчику можно найти пару, т.е. 101-элементное подмножество, которое и требуется по условию.
7⁷⁷⁷+1 число делится на 5, если оно оканчивается на нуль или на 5. посмотрим на что оканчивается 7 в любой степени: 7¹=7 7²=..9 7³=..3 7⁴=..1 7⁵=..7
7¹ и 7⁵ - оканчиваются на 7, значит период повтора цифр=4 Итак 7 в любой степени может оканчиваться только на 7,9,3 или 1 теперь делим нужную степень на период повтора: 777/4=194 (ост. 1) остаток говорит о том, что если бы мы взяли число (777-ост.), то есть 777-1=776, то это число поделилось нацело на 4, 776/4=194. у нас период повтора 4, значит если 776 делится нацело на 4, то 7⁴ и 7⁷⁷⁶ - оканчиваются на 1. отсюда 7⁷⁷⁶⁺¹ и 7⁴⁺¹ ⇒ 7⁷⁷⁷ и 7⁵ или 7⁷⁷⁷ и 7¹ - оканчиваются на 7. 7⁷⁷⁷+1=..7+1=...8 число 7⁷⁷⁷+1 - оканчивается на 8, следовательно оно не делится на 5-ч.т.д.
Доказательство. Пусть еще не все мальчики - женихи, на первом шаге выберем любого мальчика без невесты, а он пригласит всех девочек, с которыми он знаком. На каждом последующем шаге будем добавлять в рассмотрение женихов всех выбранных девочек, а они тоже пригласят всех девочек, с которыми они знакомы.
Тогда:
1. На каком-то шаге мы выберем девочку без жениха (всякий раз, если в группе есть m мальчиков, будет не менее m девочек. Если всё время у всех девочек будут женихи, то равно или поздно в группе будут все k мальчиков и, соответственно, не менее k девочек. Ну а поскольку невест не больше k - 1, то хотя бы у одной не будет жениха).
2. Найдя девочку без жениха, поженим её с тем, кто её пригласил. Оставшуюся без пары девочку поженим с тем, кто пригласил её, и так далее. В конце концов мальчик, изначально не умевший пары, получит невесту, а все мальчики - женихи, останутся женихами.
Повторяя подобные операции можно найти всем мальчикам пару.
А теперь к задаче ;)
Пусть 100-элементные подмножества - мальчики, 101-элементные подмножества - девочки. Будем говорить, что мальчик знает девочку, если они отличаются на один элемент (например, {1, 2, ..., 100} знает {1, 2, ..., 101}).
Заметим, что любые m мальчиков суммарно знают не менее m девочек: каждый знает 1916 девочек, а общих знакомых девочек, посчитанных дважды, на каждого не больше 101.
Тогда по лемме каждому мальчику можно найти пару, т.е. 101-элементное подмножество, которое и требуется по условию.
число делится на 5, если оно оканчивается на нуль или на 5.
посмотрим на что оканчивается 7 в любой степени:
7¹=7
7²=..9
7³=..3
7⁴=..1
7⁵=..7
7¹ и 7⁵ - оканчиваются на 7, значит период повтора цифр=4
Итак 7 в любой степени может оканчиваться только на 7,9,3 или 1
теперь делим нужную степень на период повтора:
777/4=194 (ост. 1)
остаток говорит о том, что если бы мы взяли число (777-ост.), то есть 777-1=776, то это число поделилось нацело на 4, 776/4=194.
у нас период повтора 4, значит если 776 делится нацело на 4, то 7⁴ и 7⁷⁷⁶ - оканчиваются на 1.
отсюда 7⁷⁷⁶⁺¹ и 7⁴⁺¹ ⇒ 7⁷⁷⁷ и 7⁵ или 7⁷⁷⁷ и 7¹ - оканчиваются на 7.
7⁷⁷⁷+1=..7+1=...8
число 7⁷⁷⁷+1 - оканчивается на 8, следовательно оно не делится на 5-ч.т.д.