Без деление кажете колко е остатъка 19062317 : 99

[dgs]

Автора на тази задача не съм аз. Доколкото ми е известно, казва се Камен. Преди време, беше публикувана (и решена) като развлекателна задача в друг форум.

copy/paste
Можете ли наум, без да използвате деление, да кажете колко е остатъка от делението на 19062317 на 99

[Реклама]

[Пафнутий]

Да Достатъчно е да се знаят признаците за деление на 11 и 9

[dgs]

Ти хубаво ми намигаш, ама аз не ги знам признаците за деление на 9 и 11. Което не ми пречи да кажа какъв е търсения остатък.
А и в задачата не се пита "дали числото се дели на 99", а "колко е остатъка при деление на 99"

Да добавя, че простото умножение на остатък при делене на 9 и остатък при делене 11 не ни дава верен отговор.
Защо ? - вземи за пример остатъка при "23 делено на 12" и съответно "23 делено на 3" и "23 делено на 4"

[Пафнутий]

[ганка симеонова]

Това е ясно, но какво следва за остатъка?

[dgs]

Извинявай, редактирах малко моя предишен пост без да забележа, че вече си писал след мен.

Това обаче не ми пречи да кажа:
Не, не съм доволен. Ще бъда доволен, когато смятайки наум ми кажеш остатъка.

Твърдиш, че това можеш да го правиш наум за осемцифрени числа, така ли ?
По тоз начин намирам най-близкото число, делящо се на 99
Не вярвам !

[Пафнутий]

Кой е казал, че не смятам наум? Не мога да сметна сбора от цифрите ли? Друг е въпросът, че мога НАУМ да го разделя и по обикновения начин. Предполагам, че имаш твой начин, който се различава от моя, но недей да отхвърляш всички други предложения

[dgs]

Извинявай, не искам да те разстройвам.

Нека приемем, че повечето хора (и аз включително) сме по-глупави от теб и не сме в състояние да извършваме такива сложни сметки наум с осемцифрени числа – "намиране на най-близкото число делящо се на 99".
И понеже сме и по-мързеливи, правим нещо друго за целта. (Мързеливи сме, ама маалко сме се понапънали и сме измислили някакъв простичък алгоритъм за намиране на остатъка наум)

[Пафнутий]

Напълно съм съгласен, че има някакъв по-простичък метод В това спор няма.Просто не ми дойде на акъла нищо друго
ПП Ако докажа метод за деление на 99=100-1 ще се зачита ли за решение? Знам, че никак няма да е красиво решението

[dgs]

Ами не знам, пробвай.

Между другото, вече мога
"много бързо наум да намеря най-близките две(*) числа делящи се на 99".
Предполагам, сещаш се как го правя - първо намирам набързо остатъка, а после и числата

(*) "най-близките две числа" - най-близкото по-малко и най-близкото по-голямо

[Пафнутий]

Като се замисля доказването на признака няма да е толкова лесно И все пак не може ли по-лесно да намерим остатъка като разделим на [tex]100[/tex] на частно с остатък (100q+r) (това на ум всеки трябва да го може) и понеже [tex]100=99+1[/tex], после да пресметнем [tex]q+r[/tex] (това става също наум) и вече остатъка на [tex]q+r[/tex] при деление с 99 съвпада с търсения (понеже е само 8 цифрено числото, то и това трябва да стане на ум, ако не- повтаряме процедурата, докъде достигнем до достатъчно лесно число)
Пример: Имаме числото [tex]N[/tex].
Представяме [tex]N=100q+r[/tex]
Тогава [tex]N\equiv q+r(mod 99)[/tex] (т.е [tex]N[/tex] дава същия остатък като [tex]q+r[/tex] при деление на 99)
Сега задачата:
[tex]19062317 =190623.100+17[/tex]
[tex]190 640\equiv x(mod 99)[/tex]
[tex]190 640 =1 906.100+ 40[/tex]
[tex]1946\equiv x(mod99)[/tex]
[tex] 1946=19.100+46[/tex]
[tex]46+19\equiv x(mod 99)\Rightarrow x=65[/tex]

ПП Прав беше, че трябва малко да се понапъна

[Пафнутий]

След като намерих бърз алгоритъм, който решава задачата би ли казал твоя?

[dgs]

Бърз ли ?
Хмм, ... така като гледам q е шестцифрено (ако N е осемцифрено).
Което все пак е добра новина, дотук смъкна цели два разряда. А нататък ?

[Пафнутий]

Виж горе!!! Едитнах го Помислих, че ще се досетиш, че това можем да го повтаряме, докато достигнем до нещо "приятно"

[dgs]

Едитни го пак, че имаш грешки (правописни). Провери и с калкулатор ако не вярваш за грешките

[Пафнутий]

Готово Сега би ли казал твоя? Точно 65 е

[b1ck0]

Колко е остатъка ... аз мисля че е 20 ... ?

Edit: Не мога даже да събирам ....

[tex]N = 19062317 [/tex]

[tex]N_1 = 190623 + 17 = 190640 [/tex]

[tex]N_2 = 1906 + 40 = 1946 [/tex]

[tex]N_3 = 19 + 46 = 65 [/tex] ....

[evgeni91]

[dgs]

Чудесен алгоритъм. Лошото е, че някои числа все още са големи.
Ти самия сбърка вече когато го писа, а пък наум ще се сбърка още по-лесно.
Ако се понапънеш още съвсем малко, ще стигнеш до нещо още по-просто. Няма да го казвам (засега), за да не ти разваля кефа да си го откриеш сам.

Няколко човека сме писали едновременно.

[Пафнутий]

[dgs]

b1ck0,
можеш ли да се обосновеш защо това което си написал като сметки е вярно в общия случай за произволно N ?

До останалите пишещи в момента:
Не знам дали забелязвате, има малка но съществена разлика при b1ck0 - той на практика сумира само двуцифрени числа !
Което лесно се прави и наум !

Редакция:
b1ck0,
Май съм се объркал нещо в тоя мой пост - като че ли и при теб не са съвсем двуцифрени в общия случай. Сега на второ четене, виждам, че при теб е същото като при stanislav atanasov

[dgs]

Обърках някои неща в предишния ми пост. Затова ще публикувам решението, такова каквото вече е публикувано в другия форум. При това решение, добре се вижда алгоритъма при който има събиране само на двуцифрени числа и евентуално накрая едно деление при общия случай.


copy/paste

[Пафнутий]

По горната идея можем да съставим следния признак за делимост.
Едно естествено число [tex]S[/tex] се дели на [tex]\underbrace{999...99}_{n}[/tex], ако след като го разделим на [tex]N[/tex]-торки, сборът на тези [tex]N[/tex]-торки е число, делящо се на
[tex]\underbrace{999...99}_{n}[/tex]
Доказателство: Всяко естествено число може да се представи във вида [tex]S=\sum_{i=1}^s 10^{n^i}.d_{i}=\underbrace{999...99}_{n}A+\sum_{i=1}^s d_{i}[/tex] , където [tex]d_{i}[/tex] e най-много [tex]n[/tex]-цифрено. QED