Пятициферные комбинации

Golyadkin · Post by **Golyadkin** » 12 Feb 2007 23:22

На бумажных карточках написаны числа от 11111 до 99999. На каждой карточке - ровно одно число. Каждое число из указанного диапазона присутствует в колоде ровно один раз.
Карточки тщательно перемешивают и выкладывают цепочкой.
Доказать, что получившееся длинное число не является степенью двойки

venco · Post by **venco** » 13 Feb 2007 01:43

Степень двойки не может делиться на 3.

Golyadkin · Post by **Golyadkin** » 13 Feb 2007 02:46

Увы. Это не решение. Исходное число тоже на три не делится.

Hoochin · Post by **Hoochin** » 13 Feb 2007 03:20

Golyadkin wrote:На бумажных карточках написаны числа от 11111 до 99999. На каждой карточке - ровно одно число. Каждое число из указанного диапазона присутствует в колоде ровно один раз.
Карточки тщательно перемешивают и выкладывают цепочкой.
Доказать, что получившееся длинное число не является степенью двойки

Длина етого числа 444445. T.e., 1.111E44444<X<1E44445
Log2 от 1.11*(10 в 44444) = 44444 log2(10)+log1.11 = 44444*3.321928095+.15=147639.9xx
Log2 от (10 в 44445) = 44445 log2(10) = 44445*3.321928095=147643.0xx

Итого: 2 в 147640, 147641, 147642, либо 2 в 147643.
Всего 4 числа (степени 2-ки) такой длины.

Как проверить? Или как записать ети числа - не знаю...

Hoochin · Post by **Hoochin** » 13 Feb 2007 04:34

Другой спосок, который мне кажется должен сработать, ето найти остаток или остатки от деления етого длинного числа на 6. Степень двойки должна давать остаток или 2, или 4. 2 mod 6 or 4 mod 6.

Сумма всех чисел в етом числе 493828395 = 44444*(11111+99999)+55555, значит наше число дает при делени на 3 остаток 2.
Нечетные числа не рассматриваем, так что:
0 mod 2 AND 2 mod 3, след-но:

2 mod 6. Не работает етот метод.

venco · Post by **venco** » 13 Feb 2007 05:39

Golyadkin wrote:Увы. Это не решение. Исходное число тоже на три не делится.

Пардон, поспешил.

Степень двойки не делится на 41.

Hoochin · Post by **Hoochin** » 13 Feb 2007 05:51

venco wrote:[
Степень двойки не делится на.

nevermind.
11111 and 99999 both have 0 mod XX

Golyadkin · Post by **Golyadkin** » 13 Feb 2007 13:50

venco wrote:
Golyadkin wrote:Увы. Это не решение. Исходное число тоже на три не делится.

Пардон, поспешил.

В принципе, правильно. А как получили? Потому что у меня немного другое решение.

venco · Post by **venco** » 13 Feb 2007 15:53

Использовал признак делимости на ХХ в 100000-ричной системе счисления.

Hoochin · Post by **Hoochin** » 13 Feb 2007 22:29

venco wrote:Использовал признак делимости на ХХ в 100000-ричной системе счисления.

Ну ладно уже: XX=41;

Те вычисления что я приводил, вот:
493828395 = 44444*(11111+99999)+55555

Все написанные выше числа делятся на 41.

Обьясните мне, хочу знать, какой признак делимости на 41.

Иоп · Post by **Иоп** » 14 Feb 2007 00:57

venco wrote:Использовал признак делимости на ХХ в 100000-ричной системе счисления.

Извините за оффтоп, просто напомнило анекдот:
- Как мне представить n-мерное пространство?
- Это очень просто. Представьте (n-1)-мерное пространство и добавьте еще одно измерение.

venco · Post by **venco** » 14 Feb 2007 04:10

Hoochin wrote:
venco wrote:Использовал признак делимости на ХХ в 100000-ричной системе счисления.

Ну ладно уже: XX=41;

Те вычисления что я приводил, вот:
493828395 = 44444*(11111+99999)+55555

Все написанные выше числа делятся на 41.

А ведь без применения признака делимости на 41 в 10000-ричной системе из вышеприведённого ещё не следует ответ.

Обьясните мне, хочу знать, какой признак делимости на 41.

А такой же, что и делимость на 3 в 10-тичной системе:
число делится на 41 <-> сумма его 10000-ричных цифр делится на 41.

Hoochin · Post by **Hoochin** » 14 Feb 2007 05:36

venco wrote:
Hoochin wrote:
venco wrote:Использовал признак делимости на ХХ в 100000-ричной системе счисления.

Ну ладно уже: XX=41;

Те вычисления что я приводил, вот:
493828395 = 44444*(11111+99999)+55555

Все написанные выше числа делятся на 41.

А ведь без применения признака делимости на 41 в 10000-ричной системе из вышеприведённого ещё не следует ответ.
- Я ето не утверждал. Интересно было что за метод с 5-и значными числами было и есть. 1/41 - имеет период 5, не так ли?
Обьясните мне, хочу знать, какой признак делимости на 41.

А такой же, что и делимость на 3 в 10-тичной системе:
число делится на 41 <-> сумма его 10000-ричных цифр делится на 41.

Мда, етого я как не математик и не программер на понял.
"Киса, Вы мне как художник - художнику. Вы рисовать умеете?"
P.S. "его 10000-ричных цифр" - ето каждой пятой, что ли?

Prist · Post by **Prist** » 14 Feb 2007 18:05

venco wrote:число делится на 41 <-> сумма его 10000-ричных цифр делится на 41.

Вот, к примеру, 10004 (которое делится на 41) в системе с основанием 10000 будет, очевидно, выглядеть как 14. И сумма его цифр ни на что не делится :pain1:

olg2002 · Post by **olg2002** » 14 Feb 2007 21:54

Признак делимости на 41 - "red herring" (с таким же успехом можно было говорить о "признаке делимости на 271").

Большое число записываем в виде:

N = n11111 + n11112*10^5 + n11113*(10^5)^2 + ...n99999*(10^5)^88888,

где n11111..n99999 - некоторая перестановка исходных чисел 11111..99999.
Все числа (10^5)^i имеют остаток 1 при делении на 99999, поэтому N можно записать как:

N = n11111 + n11112 + n11113 + ... + n99999 + K*99999

Сумма всех чисел n11111..n99999 от перестановки не зависит и равна, как уже отметили, (11111+99999)*88889/2 = 55555*88889. Таким образом,

N = 55555*88889 + K*99999,

а значит делится на 11111 (в том числе на 41 и 271) и не может быть степенью 2-ки.

venco · Post by **venco** » 14 Feb 2007 23:50

Prist wrote:
venco wrote:число делится на 41 <-> сумма его 10000-ричных цифр делится на 41.

Вот, к примеру, 10004 (которое делится на 41) в системе с основанием 10000 будет, очевидно, выглядеть как 14. И сумма его цифр ни на что не делится

Это потому что там опечатка, дожны быть 100000-ричные цифры.

venco · Post by **venco** » 14 Feb 2007 23:52

olg2002 wrote:Признак делимости на 41 - "red herring" (с таким же успехом можно было говорить о "признаке делимости на 271").

Правильно, но делимость на 41 выглядит загадочнее, чем на 11111.

Hoochin · Post by **Hoochin** » 15 Feb 2007 18:21

venco wrote:
olg2002 wrote:Признак делимости на 41 - "red herring" (с таким же успехом можно было говорить о "признаке делимости на 271").

Правильно, но делимость на 41 выглядит загадочнее, чем на 11111.

Загадочнее? А правилно ли ето вааще?
btw, "red herring' does not exsist.

Hoochin · Post by **Hoochin** » 15 Feb 2007 22:05

Hoochin wrote:
venco wrote:
olg2002 wrote:Признак делимости на 41 - "red herring" (с таким же успехом можно было говорить о "признаке делимости на 271").

Правильно, но делимость на 41 выглядит загадочнее, чем на 11111.

Загадочнее? А правилно ли ето вааще?
btw, "red herring' does not exsist.

were you kidding about "41"?

...

Hoochin · Post by **Hoochin** » 15 Feb 2007 22:44

venco · Post by **venco** » 15 Feb 2007 23:23

Ок, подробнее про признак делимости на 41.

Все мы знаем признак делимости десятичных чисел на 3 и 9 - если сумма цифр делится, то и само число делится.
На самом деле аналогичные признаки делимости есть для любой системы счисления D > 2.
Только вместо 3 и 9, будут любые делители числа (D-1).
Число из исходной задачи можно рассмотреть в 100000-ричной системе счисления, при этом цифрами будут 5-ти значные числа 11111-99999.
В этой системе счисления есть признаки делимости по сумме цифр на делители числа 99999, 41 в их числе.
Поскольку сумма чисел 11111-99999 (она же - сумма цифр большого числа в 100000-ричной системе счисления) делится на 41 (и на 11111), то и число составленное из них тоже будет делится на 41 (и на 11111), независимо от порядка этих 5-ти значных чисел.
Следовательно, целой степенью двойки это длинное число быть не может.

Привет

Пятициферные комбинации

Пятициферные комбинации

Re: Пятициферные комбинации