Есть 2n карточек с номерами от 1 до 2n. Зритель выкладывает их в ряд на столе. Ассистент фокусника может поменять местами какие-то две карты на выбор (или не делать ничего). После этого все карты переворачиваются рубашкой вверх. Заходит фокусник, зритель называет ему любое число от 1 до 2n. Фокусник сделав не более чем n попыток находит карточку с указанным числом. (Перевернуть любую карту — это одна попытка). Как ассистент и фокусник могут договориться, чтобы фокус всегда получался?
Решение
Количество различных последовательностей состоящих из четных и нечетных карточек из колоды = 2 + n * (n - 2).
2. Фокусник и ассистент сопоставляют каждой последовательности из п.1 номер от 1 до 2 * n.
3. Таким образом, если ассистент сообщит фокуснику число от 1 до 2 * n (например, положив карточку с этим номером в самое начало, либо ничего не сделав, если она уже там), то число перебираемых фокусником последовательностей уменьшится в 2 * n раз.
4. (2 + n * (n - 2)) / 2 * n = n - 1 - 1 / n, что есть максимальное количество необходимых фокуснику проверок для точного определения позиции искомой карточки в ряду после просмотра первой карточки.
5. Фокусник проверяет карточки исходя из четности названного зрителем числа.
Пусть m/n — несократимая дробь (m, n — натуральные числа).a) Докажите, что если n является произведением степеней 2 и 5, то десятичная запись дроби m/n конечна.
Если n является произведением степеней 2 и 5, то десятичная запись дроби конечна, например: 3/25=3*4/25*4=0,12 b) Пусть n не является произведением степеней 2 и 5. Докажите, что идущие после запятой цифры ее десятичной записи образуют бесконечную периодическую последовательность
. (Периодичность не обязана быть чистой, то есть может начинаться не сразу после запятой.)
Действительно, если m/n = a/10b , то 10bm = an; рассмотрев любой отличный от 2 и 5 простой делитель p числа n, приходим к противоречию: an кратно p, а равное ему число 10bm – не кратно. Например: 3/7=0,(428571) в периоде.c) Докажите, что длина периода меньше n.
Чтобы получить первую цифру после запятой, мы приписываем к m нуль (т.е. умножаем m на 10) и делим (с остатком) полученное число на n. Вообще весь процесс деления уголком – повторяемое вновь и вновь умножение очередного остатка на 10 и деление (с остатком) на n. Если на каком-то шаге получится нулевой остаток, то дробь – конечная. Конечную дробь, приписав к ней справа бесконечно много нулей, естественно считать периодической с периодом длины 1. По условию, 1 ≤ n – 1, так что в этом случае утверждение теоремы выполнено. Если же процесс деления никогда не закончится, то будут получаться только ненулевые остатки, т.е. числа от 1 до n – 1. Значит, не позже чем на n-м шаге остаток повторится
Задать вопрос
на новый заказ в Автор24.
