"Дорогие радиослушатели, пишет нам..." - кажется так начинался один из развесёлых анекдотов еще старых-недобрых советских времён. Так вот, не так давно один из наших радио-интернет-ЖЖ-слушателей где-то тут пожаловался, что у него истекает лицензия на KIS и что пора бы снова какие-нибудь мозговые головоломки позадавать - это он так надеется чисто ментальными упражнениями [золотой] годовой ключик заполучить, - похвально! Их есть у нас - и задачек, и ключиков. К тому же на авто-мото-тему буквально только что произошел очередной конкурс, пора и на тему арифметически-математического тоже посоревноваться.
Согласен я по всем направлениям с нашими радиослушателями, что-то мы давно не упражняли серое вещество головного мозга - как бы оно из-за этого не загустело и не забродило! Этого я допустить никак не могу, посему вот вам следующая задачка:
1. Доказать, что если состоящее только из единиц число (111...111) делится на 2017, то оно же делится и на 9.
И сразу следом ->
2. Найти (без программирования, математическими выкладками) минимальное такое число. То есть, число, которое состоит только из единиц и делится без остатка на 2017 и 9
Еще раз объясняю, решения на перлах-джавах-питонах рассматриваются только как дополнительная проверка математическим доказательствам. Решение должно быть таким, чтобы его можно было воспроизвести карандашом на листе бумаги А4.
Ага?
Самые точные, оригинальные и остроумные ответы будут отмечены ценными призами, благодарственными грамотами и словами восхищения! :) Ну, поехали!
Согласен я по всем направлениям с нашими радиослушателями, что-то мы давно не упражняли серое вещество головного мозга - как бы оно из-за этого не загустело и не забродило! Этого я допустить никак не могу, посему вот вам следующая задачка:
1. Доказать, что если состоящее только из единиц число (111...111) делится на 2017, то оно же делится и на 9.
И сразу следом ->
2. Найти (без программирования, математическими выкладками) минимальное такое число. То есть, число, которое состоит только из единиц и делится без остатка на 2017 и 9
Еще раз объясняю, решения на перлах-джавах-питонах рассматриваются только как дополнительная проверка математическим доказательствам. Решение должно быть таким, чтобы его можно было воспроизвести карандашом на листе бумаги А4.
Ага?
Самые точные, оригинальные и остроумные ответы будут отмечены ценными призами, благодарственными грамотами и словами восхищения! :) Ну, поехали!
2018-03-17 09:28 (UTC)
2018-03-17 11:59 (UTC)
Указанное число из t единиц можно представить как (10^t - 1) / 9 и по условию оно сравнимо с нулем по модулю 2017. 2017 число простое, следовательно 10^t сравнимо с 1 по модулю 2017.
Малая теорема Ферма утверждает, что t=2016 будет нужным показателем степени. Более того, мультипликативный порядок ненулевого остатка будет делителем числа 2016 = 2^5 * 3^2 * 7. Степени образуют циклическую группу. Фактически же наша задача состоит в том, чтоб показать, что для числа 10 мультипликативный порядок L = 2016. Тогда со всей очевидностью следует решение задачи, поскольку любое t будет делиться на L, а значит и соответствующее число будет делиться на 9, поскольку его сумма цифр будет кратна 2016, т.е. тоже делиться на 9. Ну и минимальное число так же будет представляться записью из 2016 единиц.
Ну а поскольку 10 не является квадратичным вычетом, не является вычетом 3й или 7й степени (делители 2016), то его мультипликативный порядок не может быть делителем 2016 отличным от него самого.
(последнее утверждение проверялось численно, но стоит подумать как и в этом вопросе обойтись без компьютера)
2018-03-17 13:58 (UTC)
2018-03-18 07:54 (UTC)
А почему Вас t=16 заинтересовало?
2018-03-17 14:47 (UTC)
Именно так. У меня получилось только с помощью калькулятора, чисто карандаш+бумага нет.. Там вычислений немного, но утомляет.
2018-03-17 12:00 (UTC)
А дальше просто - берешь и делишь уголком 1111...11 на 2017. Вследствие вышеуказанного процесс сойдется (правда, непонятно, за какое время:)). Очевидно, это будет минимальное такое число из одних единиц. Поделится ли оно на девять - ну, там и посмотрим:) (я понимаю, что доказательство делимости на девять не очень красивое - но, в принципе, допустимое)
2018-03-18 07:49 (UTC)
Для этого число единиц должно быть кратно девяти.
2018-03-18 11:43 (UTC)
Просто тот вариант, который я озвучил, помимо того, что на одном листе А4 не реализуется, еще и дает ответы на вопросы в обратном порядке: сначала находится искомое число, а уж потом проверяется, делится ли оно на девять.
2018-03-17 14:30 (UTC)
Да, халявы в этот раз не будет... Все что приходит на ум:
Дорогая передача,
Во субботу, чуть не плача,
Вся Канатчикова дача
К телевизору рвалась.
...
Может лучше про реактор?
Про любимый лунный трактор?
2018-03-17 14:46 (UTC)
Надо отметить, что нигде не сказано, что число 11111...111 не может быть двоичным, 2017 - восьмеричным, а 9 - шестнадцатиричным.
2018-03-17 14:48 (UTC)
2018-03-17 15:48 (UTC)
Блин... А я уже размечтался :)
2018-03-18 09:10 (UTC)
2018-03-18 15:59 (UTC)
2018-03-18 10:43 (UTC)
(m,n)=1 => m^f(n)=1 (mod n).
=>
сумма начальных (f(n)-1) штук слагаемых вида i*m^n делится на n.
Edited at 2018-03-18 10:44 (UTC)
2018-03-18 12:04 (UTC)
(10^x-1)/9=11...111
найти min (z)
((10^z-1)/9)/2017=j
10^z=9*2017*j+1
z,j - целые положительные
2018-03-18 12:20 (UTC)
3*j+1=0
=>
j=3
вроде как ))
10^z=9*2017*3+1
Edited at 2018-03-18 12:22 (UTC)
2018-03-18 12:32 (UTC)
решал/делил в столбик
2018-03-18 15:18 (UTC)
На одном листочке там не помещается, поэтому пишу итоговую цифру:
получается число с количеством единиц = 10080.
Это минимальное число, которое без остатка делится на 2017.
Т.к. число с 9 единицами 111111111 делится на 9 (=12345679),
то в числе с количеством единиц = 10080 число 111111111 встречается ровно 10080/9= 1120 раз,
т.е. оно делится на 9.
---------------
Ответ: минимальное число, которое делится на 2017 и на 9, это
111111......1111111 (10080 единиц)
========================================
1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
1 0 0 8 5
1 0 2 6 1
1 0 0 8 5
1 7 6 1 1
1 6 1 3 6
1 4 7 5 1
1 4 1 1 9
6 3 2 1
6 0 5 1
2 7 0 1
2 0 1 7
6 8 4 1
6 0 5 1
7 9 0 1
6 0 5 1
1 8 5 0 1
1 8 1 5 3
.......
Re: решал/делил в столбик
2018-03-18 15:47 (UTC)
Хотя, конечно, и из 5*2016 тоже делится, да.
Re: решал/делил в столбик
2018-03-18 16:43 (UTC)
у меня оказывается промежуточные вычисления затерлись последующими.
Сейчас посмотрел внимательнее, там было:
2016
4032
6048
8064
10080
Т.е., минимальное число с 2016 единицами и оно делится на 9.
===============
Ещё нес десятков чисел в порядке возрастания по количеству единиц:
4032
6048
8064
10080
12096
14112
16128
18144
20160
22176
24192
26208
28224
30240
32256
34272
36288
38304
40320
42336
44352
46368
48384
50400
52416
54432
56448
58464
60480
62496
64512
66528
68544
70560
72576
74592
76608
78624
80640
82656
84672
86688
88704
90720
92736
94752
96768
98784
100800
102816
104832
106848
108864
110880
Re: решал/делил в столбик
2018-03-18 17:35 (UTC)
Нашёл только пару чисел:
111111840
311111136
но у них не все цифры единицы.
Шутка ))
2018-03-22 09:50 (UTC)
он огорчился и не стал продолжать беседу в этом топике :)
2018-03-24 23:12 (UTC)