Арифметическое многоединичие.

Previous Entry Поделиться Next Entry
17 марта, 11:25
e_kaspersky
"Дорогие радиослушатели, пишет нам..." - кажется так начинался один из развесёлых анекдотов еще старых-недобрых советских времён. Так вот, не так давно один из наших радио-интернет-ЖЖ-слушателей где-то тут пожаловался, что у него истекает лицензия на KIS и что пора бы снова какие-нибудь мозговые головоломки позадавать - это он так надеется чисто ментальными упражнениями [золотой] годовой ключик заполучить, - похвально! Их есть у нас - и задачек, и ключиков. К тому же на авто-мото-тему буквально только что произошел очередной конкурс, пора и на тему арифметически-математического тоже посоревноваться.

Согласен я по всем направлениям с нашими радиослушателями, что-то мы давно не упражняли серое вещество головного мозга - как бы оно из-за этого не загустело и не забродило! Этого я допустить никак не могу, посему вот вам следующая задачка:

1. Доказать, что если состоящее только из единиц число (111...111) делится на 2017, то оно же делится и на 9.

И сразу следом ->

2. Найти (без программирования, математическими выкладками) минимальное такое число. То есть, число, которое состоит только из единиц и делится без остатка на 2017 и 9

Еще раз объясняю, решения на перлах-джавах-питонах рассматриваются только как дополнительная проверка математическим доказательствам. Решение должно быть таким, чтобы его можно было воспроизвести карандашом на листе бумаги А4.

Ага?

Самые точные, оригинальные и остроумные ответы будут отмечены ценными призами, благодарственными грамотами и словами восхищения! :) Ну, поехали!

Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»

  • 1+12 ответов про То Самое.

    Итак, мои версии ответов на вопрос "как попасть на Северный (и Южный) полюс". Самый простой и самый дешёвый способ -> C1: купить билет на…

  • 2+15 вопросов про То Самое.

    Прежде чем бежать по рассказам дальше, я сделаю запятую. Вернее будет сказать... уже сделал – она чуть раньше по тексту поставлена. Я бы даже выделил…

  • В условиях стабильного климата.

    Здесь немного ветрено, но в целом климат стабильный и уверенный в себе, что не может не радовать. Приятно осознавать, что ты здесь хозяин себе.…


Давайте попробуем:

Указанное число из 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 отличным от него самого.
(последнее утверждение проверялось численно, но стоит подумать как и в этом вопросе обойтись без компьютера)

В конце не нолик, а единичка.
А почему Вас t=16 заинтересовало?

> последнее утверждение проверялось численно, но стоит подумать как и в этом вопросе обойтись без компьютера

Именно так. У меня получилось только с помощью калькулятора, чисто карандаш+бумага нет.. Там вычислений немного, но утомляет.

Ну, то, что для любого простого числа найдется такое число из одних единиц, которое нацело разделится на это простое, я под Новый год доказывал.
А дальше просто - берешь и делишь уголком 1111...11 на 2017. Вследствие вышеуказанного процесс сойдется (правда, непонятно, за какое время:)). Очевидно, это будет минимальное такое число из одних единиц. Поделится ли оно на девять - ну, там и посмотрим:) (я понимаю, что доказательство делимости на девять не очень красивое - но, в принципе, допустимое)

А в чём проблемы с делимостью на 9?
Для этого число единиц должно быть кратно девяти.

Понятно, что кратно 9.
Просто тот вариант, который я озвучил, помимо того, что на одном листе А4 не реализуется, еще и дает ответы на вопросы в обратном порядке: сначала находится искомое число, а уж потом проверяется, делится ли оно на девять.

Да, халявы в этот раз не будет... Все что приходит на ум:

Дорогая передача,

Во субботу, чуть не плача,

Вся Канатчикова дача

К телевизору рвалась.

...

Может лучше про реактор?

Про любимый лунный трактор?


Надо отметить, что нигде не сказано, что число 11111...111 не может быть двоичным, 2017 - восьмеричным, а 9 - шестнадцатиричным.


Если в одном условии используются цифры 0,1,2,7,9 и не указано другое, то по умолчанию принимается десятичная система.

Интересно, кто победил в прошлом конкурсе Цифровой 2018? Кажется, победитель не был объявлен.

Там было несколько конкурсов. В некоторых народ активничал - и были призёры. Но с мыслями у народа было тухло - то и подарков не было.

среди бесконечного множества чисел записанных одной цифрой "i" в системе счисления с основанием m найдется бесконечно много чисел, делящихся на произвольное n, взаимно простое с m.

(m,n)=1 => m^f(n)=1 (mod n).
=>
сумма начальных (f(n)-1) штук слагаемых вида i*m^n делится на n.

Edited at 2018-03-18 10:44 (UTC)

(10^x-1)=100...000=99...999
(10^x-1)/9=11...111

найти min (z)

((10^z-1)/9)/2017=j

10^z=9*2017*j+1

z,j - целые положительные

9*7=63
3*j+1=0
=>
j=3
вроде как ))

10^z=9*2017*3+1

Edited at 2018-03-18 12:22 (UTC)

решал/делил в столбик

Y K

2018-03-18 15:18 (UTC)

Мне уже 7-й десяток, поэтому я решал/делил в столбик.
На одном листочке там не помещается, поэтому пишу итоговую цифру:
получается число с количеством единиц = 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: решал/делил в столбик

sir_derryk

2018-03-18 15:47 (UTC)

На самом деле на 2017 делится число из 2016 единиц.
Хотя, конечно, и из 5*2016 тоже делится, да.

Re: решал/делил в столбик

Y K

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: решал/делил в столбик

Y K

2018-03-18 17:35 (UTC)

Хотел найти красивое число из единиц, которое указывает, сколько единиц в числе вышеуказанной задачи.
Нашёл только пару чисел:
111111840
311111136
но у них не все цифры единицы.


Интеллектуальный уровень собеседников видимо поразил Евгения Валентиновича в самое сердце,
он огорчился и не стал продолжать беседу в этом топике :)


Поскольку внятного решения предложено не было, даже близко не подползли - то призы и подарки сегодня-завтра будут раздаваться в соседней ветке про Формулу-1.

?

Log in

No account? Create an account