Странное задание C6

[VAL]

Как говорится, накаркал!
Теперь и в самом деле (без первоапрельских штучек) ко мне обратились за помощью с рядом заданий C6.
У некоторых время решения равно времени прочтения условия. Над другими пришлось посидеть, иногда основательно. А одно...
Мне кажется, что оно здесь уже пробегало, но попытка найти соответствующий топик успехом не увенчалась. Вот это задание:

Цитата:

Найдите все натуральные числа, являющиеся степенью двойки, такие, что после зачеркивания первой цифры их десятичной записи снова получается десятичная запись числа, являющегося степенью двойки.

Разумеется, в уме находится вариант 64.
То что других решений нет я умею доказывать так:
Пусть $2^n=c10^k+2^m$. Ясно, что $c10^k=c_15^t2^m$, где $c_15^k+1$ - степень двойки, a $c_1$ - нечетная цифра (лекго показать, что это либо тройка, либо семерка). В противном случае в правой части будет нечетный множитель.
Итак, надо показать, что $c_15^t+1=2^s$, где $c_1=3$ либо $c_1=7$, возможно только при $t=1$.
По теореме Эйлера $2^{\varphi(5^t)}\equiv 1 (mod \ 5^t)$. Учитывая, что двойка является первообразным корнем по модулю $5^t$ при любом $t$, получаеем, что $\varphi(5^t)$ - наименьший натуральный показатель, при котором $2^s-1$ кратно $5^t$. Но при $t>1 \ \ 2^{\varphi(5^t)}$ гораздо больше $5^t$ и $c$ не может быть цифрой.
Так что, все доказано. Но что делать школьнику, который ничего не слышал ни про какие первообразные корни (тем более, по составному модулю)? Вряд ли составители ориентировались на решение, приведенное выше.

PS: Вообще, задания С6 во всяких пробных вариантах ЕГЭ вопиюще неоднородны. Интересно, на настоящем ЕГЭ сохранится такая же лотерея?

[ewert]

VAL в сообщении #310144 писал(а):

Разумеется, в уме находится вариант 64.То что других решений нет я умею доказывать так:

Ну прям таки и нет. А 32?...

Я эту задачу тоже видел, и она мне не понравилась. Там вот какой пафос может быть, например. Доказать, что если $2^m-1$ делится на $5^k$, то оно делится и на $15^k$. Тогда, начиная с 7-й где-то степени отсутствие решений уже очевидно. Но это -- сильное огрубление, да и тоже морока (к тому же я так и не доказал это для $k>1$).

В общем, нехорошая задача.

[VAL]

ewert в сообщении #310147 писал(а):

VAL в сообщении #310144 писал(а):

Разумеется, в уме находится вариант 64.То что других решений нет я умею доказывать так:

Ну прям таки и нет. А 32?...

32 не считается
Разумеется, я имел в виду, что уравнение $c_15^t+1=2^s$ имеет единственное решение при $t=1$ (из которого получаются и 32 и 64) и не имеет решений при $t>1$. Но выразился как-то "неаккуратно"

Цитата:

В общем, нехорошая задача.

Согласен. Если при проверке ЕГЭ увижу вместо решения такой комментарий, буду оценивать в три сырых балла

[VAL]

ewert в сообщении #310147 писал(а):

Там вот какой пафос может быть, например. Доказать, что если $2^m-1$ делится на $5^k$, то оно делится и на $15^k$.

Это не так уже при $k=2$.
$2^{20}-1$ на $15^2$ не делится.

[Батороев]

ewert в сообщении #310147 писал(а):

Тогда, начиная с 7-й где-то степени отсутствие решений уже очевидно.

Наверное, здесь можно использовать: $ \log {2^{k+7}}-\log {2^{k}} > 2$,
т.е. то, что степень двойки после зачеркивания первой цифры не может быть меньше исходной степени более, чем на 6.

-- Сб апр 17, 2010 23:46:53 --

В свою очередь, если расписать число, которое вычеркнули, получаем:
$ a\cdot (2\cdot 5)^m=2^{k+6max}-2^k=2^k(2^{6max}-1)$,
где $a$ - первая цифра.
Для того, чтобы правая часть была кратна $5$, остается единственный вариант $2^4-1$ (степень двойки в скобке должна быть кратна 4).
Тогда степень вхождения пятерки в вычеркнутое число не может превышать $5^1$.
Откуда $m=1$.

[venco]

Батороев в сообщении #310665 писал(а):

Наверное, здесь можно использовать: $ \log {2^{k+7}}-\log {2^{k}} > 2$,
т.е. то, что степень двойки после зачеркивания первой цифры не может быть меньше исходной степени более, чем на 6.

Почему? Вторая цифра может быть 0.

[Батороев]

venco в сообщении #311934 писал(а):

Почему? Вторая цифра может быть 0.

Вопрос законный! Отсюда вывод: решение мое не верное.
Бум думать.

-- Чт апр 22, 2010 11:03:44 --

Понял. Решение - в формуле вычеркнутого числа:
$ a\cdot (2\cdot 5)^m = 2^{k+n}-2^k = 2^k(2^n-1)$

Если $m\geq 2$ (как предлагает рассмотреть venco), то $a$ должно быть кратно $25$, что может быть при $n$, кратном $20$.
Но если $n$ будет кратно $20$, то цифра $a$ должна быть кратна простому $11$, чего быть не может.

Решая дальше, убеждаемся, что при $n$, кратном $4$ (признак делимости на $5$), $a$ кратно $3$.
Следовательно, $a$ может быть только $3, 6, 9$.
Цифра $9$ не годится, т.к. в этом случае $n$ должно быть кратно $12$.
Но если $n$ кратно $12$, то $a$ должно быть кратно простому $13$, что также невозможно.

Таким образом, остаются два возможных вычеркнутых числа: $30$ и $60$.

У-ф-ф!

[TOTAL]

VAL в сообщении #310144 писал(а):

Пусть $2^n=c10^k+2^m$.

$c10^k=2^m(16^t -1)$, поэтому левой части запрещено делиться на что-то отличное от степеней чисел $2,3,5$

Пусть $t=2s$
Тогда $(16^{2s} -1)=(16^{s} -1)(16^{s} +1)$, где $(16^{s} +1)$ имеет запрещенный множитель

Пусть $t=2s+1$
Тогда $(16^{2s+1} -1)=(2\cdot 4^s-1)(2\cdot 4^s+1)(4\cdot 16^s+1)$, где $(2\cdot 4^s-1)$ имеет запрещенный множитель (либо надо положить $s=0$)

[VAL]

TOTAL в сообщении #311977 писал(а):

VAL в сообщении #310144 писал(а):

Пусть $2^n=c10^k+2^m$.

$c10^k=2^m(16^t -1)$

Угу. Хотя тут еще обосновать надо. Но обосновывается.

Цитата:

поэтому левой части запрещено делиться на что-то отличное от степеней чисел $2,3,5$

Почему "поэтому"? Или речь о правой части?
И почему не годится семерка?

Цитата:

Пусть $t=2s$
Тогда $(16^{2s} -1)=(16^{s} -1)(16^{s} +1)$, где $(16^{s} +1)$ имеет запрещенный множитель.

Угу.

Цитата:

Пусть $t=2s+1$
Тогда $(16^{2s+1} -1)=(2\cdot 4^s-1)(2\cdot 4^s+1)(4\cdot 16^s+1)$, где $(2\cdot 4^s-1)$ имеет запрещенный множитель

Какой?

[TOTAL]

VAL в сообщении #312220 писал(а):

TOTAL в сообщении #311977 писал(а):

$c10^k=2^m(16^t -1)$

Угу. Хотя тут еще обосновать надо. Но обосновывается.

Цитата:

поэтому левой части запрещено делиться на что-то отличное от степеней чисел $2,3,5$

Почему "поэтому"? Или речь о правой части?
И почему не годится семерка?

Правая часть делится на $3$. Поэтому левая часть тоже делится на $3$. Речь идёт о левой части. Число $c$ делится на $3$, поэтому оно не может делиться ещё ни на что кроме двойки.

VAL в сообщении #312220 писал(а):

Цитата:

Пусть $t=2s+1$
Тогда $(16^{2s+1} -1)=(2\cdot 4^s-1)(2\cdot 4^s+1)(4\cdot 16^s+1)$, где $(2\cdot 4^s-1)$ имеет запрещенный множитель

Какой?

Не имеет значения какой. Главное, что оно не делится ни на 2, ни на 3, ни на 5.

[VAL]

TOTAL в сообщении #312315 писал(а):

VAL в сообщении #312220 писал(а):

И почему не годится семерка?

Правая часть делится на $3$. Поэтому левая часть тоже делится на $3$.

Угу. Вот этот момент я прозевал.

Но, в целом, какое-то слишком зубодробительное задание по сравнению с остальными. Хотя... Вчера еще порцию C6 подкинули. И там тоже есть одно задание, которое с ходу не решилось. Точнее, решилось, но явно не так, как следовало :)