Помощ за задачка с факториали

[kod]

Озъбих се...
Вчера хлапето е имало тест за международни състезания и с една от задачите не мога да се справя...

Задачката е:
Имаме сумата на факториалите от 1! до 100!
Като от получената сума извадим един от факториалите ще получим квадрат на цяло число.
Кой от факториалите трябва да извадим...


Задачата е от тест, съставен от 10 задачи с време за решение - 60 минути, тоест, изключено е даже да се мисли за груба сила при сметките. Някаква хитрина е...
Някакви идеи?
ПС - детето е 5-ти клас, така че трябва да се реши с ограничен набор от логики.

[kod]

Страхотно обяснение от МиткоС получих, благодаря.
Нещо не може да пише във форума - някой друг има ли проблем?

[Pat]

Тест....
edit: при мен няма проблем.

[ql^2/8]

За задачката:
Сумата на факториалите от 1! до 9! е 409113.
Оттук нататък последните две цифри се запазват 13, защото факториалите след 10 завършват на поне две нули.
Понеже няма квадрат на цяло число, който да завършва на 3, очевидно трябва да извадим някой от първите 4
факториела: 1, 2, 6 или 24, по-големите от 5! включително завършват на 0 и не променят тройката.
За цяло число N може да се каже, че ако:
N завършва на 0 - N*N завършва на 00
N завършва на 1 или 9 - N*N завършва на 01, 21, 41, 61, 81
N завършва на 2 или 8 - N*N завършва на 4
N завършва на 3 или 7 - N*N завършва на 9
N завършва на 4 или 6 - N*N завършва на 6
N завършва на 5 - N*N завършва на 5
От четиримата заподозрени само 4!=24 води към целта.


Ако четете, значи мога да пиша!

[kod]

И как намираме сумата на факториалите до 9! ....

Решението на MitkoS:

Трябва да се махне 4!
Защото:
1. Квадратите на цели числа завършват на една от следните цифри - 1,4,9,6,5
2. Сумата от 3! до 100! завършва на 0. (Всеки фактуриел от 5 нагоре завършва на 0, а също 3!+4! е 30)
3. От 2. следва, че сумата от 1! до 100! завършва на цифрата 3 (3 = 1! +2!)
4. Не може квадрат на цяло число да завършва на 3 (виж 1.)
5. От 2. следва, че ако махнем фактуриел по-голям или равен на 5, то сумата пак завършва на 3. Значи трябва да махнем фактуриел по-малък от 5
6. Ако махнем:
1! --> сумата ще завършва на 2 --> не става за квадрат
2! --> сумата ще завършва на 1 --> става за квадрат
3! --> сумата ще завършва на 7 --> не става за квадрат
4! --> сумата ще завършва на 9 --> става за квадрат
7. Сега разглеждаме последните две цифри на сумата. (Тъй като съм позабравил доста неща, ползвах Ексел)
Ако махнем 2!, сумата завършва на 11
Ако махнем 4!, сумата завършва на 89
8. Ако разгледаме квадратите на числата от 1 до 100 (пак с помощта на Ексел), то няма число чиито квадрат завършва на 11.
==> няма квадрат на цяло число (без значение зали е по-чалко от 100 или по-голямо), който да завършва на 11
9. Пак разглеждаме квадратите на числата от 1 до 100 и виждаме, че има такива, които завършват на 89 - това са 17,33,67 и 83
==> за всяко едно от тези числа 17, 33, 67 е 83, като го съберем с N.10^2, то квадрата ще завършва на 89
10. От 1. до 9. ==> единствената възможност да имаме квадрат на цяло число е ако махнем 4!.
Забележка: Не твърдим че като махнем 4! ще получим квадрат на цяло число (не сме го проверили това), а твърдим, че който и друг фактуриел да махнем, то няма да е квадрат на цяло число (това вече сме го проверили от 1. до 9.)


Проблемът е в точка 7 - проверката с Ексел не е чисто решение.
Тоест, няма установено за момента решение 2! или 4!

[ql^2/8]

Именно заради точка 7 не е достатъчно да установим само последната цифра "3" - тя се "заковава" след
добавяне на 4!; трябва да поработим още 5 минути (с Ексел става за по-малко!) за да "заковем" последните
две цифри - 13, а това става след 9!
(защото числата след 10! завършват поне на 2 нули).
После е лесно да видим, че с изваждане на 2! получаваме 11, а с 4! получаваме 89.
Ако представим числото N=10k+1 (ако завършва на 1) или като N=10k-1 (ако завършва на 9).
След вдигане на квадрат (100k*k+/-20k+1) става ясно, че предпоследната цифра е четно число,
т.е. 11 не може да е "опашка" на точен квадрат.

[kod]

трябва да поработим още 5 минути (с Ексел става за по-малко!) за да "заковем" последните
две цифри - 13, а това става след 9!

Това е една от 10 задачи - другите не са по-лесни и времето за решаването на всички е 60 минути.
В случая да поработим още 5 минути е... напълно неприемливо, според мен трябва да има по-бързо и елегантно решение.
Ако няма... по-добре да стигнеш до 6-та точка и 50:50...

[ql^2/8]

Това е една от 10 задачи - другите не са по-лесни и времето за решаването на всички е 60 минути.
В случая да поработим още 5 минути е... напълно неприемливо, според мен трябва да има по-бързо и елегантно решение.
Ако няма... по-добре да стигнеш до 6-та точка и 50:50...

Е, малко е времето! Вероятно и калкулаторите са били забранени?
Няма как да се решат 10 подобни задачи за 1 час, освен ако не си
решавал вчера точно тия или много подобни на тях задачи, и вместо да мислиш,
направо започваш да пишеш решения и доказателства...

[kod]

Ето го решението 2 или 4 бре...

100! = x2 + 2 - невъзможно защото 100! завършва на 0, а x2 не може да завърши на 8
100! = x2 + 24 - възможно, защото x2 може да завърши на 6 и + 24 да завърши на 0.

[kod]

Глупости, не е така...

За 100! е така, но за сбора 1! + ...... 100! въобще не е вярно, че завършва на нула. Уффф....

[Bibi]

Когато вдигаме нечетно число на квадрат, цифрата на десетиците е винаги четна.
Значи не може точен квадрат да завърши на 11.

[kod]

Разбира се, но за целта трябва да знаеш цифрата на десетиците. А за да я знаеш, трябва да сметнеш сумата на факториалите, завършващи с по-малко от 2 нули - тоест, всички до 9!
Което леко пречи на времето, с което разполагаш за решаване.

Но това е единствения начин. Но трябва да се сетиш да не губиш време със смятане на точната сума 1! + . + 9!, а само с намирането на последните 2 числа:
1! = 1
2! = 2
3! = 6
4! = 24
5! = х20
6! = х20*6 = х20
7! = х20*7 = х40
8! = х40*8 = х20
9! = х20*9 = х80
=> последните 2 цифри са 11
Така става приемливо като трудоемкост

[kod]

Такаам, изяснихме нещата по задачата, ама днес видях учителката и се оказа, че условието е друго

Имаме произведението на факториалите от 1! до 100!
Ако един от факториалите се махне ще се получи квадрат на цяло число.
Кой от факториалите трябва да махнем...

Отговора е 50! , но ще съм благодарен някой да ми разясни по-простичко и логично защо е така

[ql^2/8]

И така, произведението на факториалите от 1 до сто, може да се представи като
1^100 * 2^99 * 3^98 * 4^97 *. . .* 99^2 * 100
четните степени са си квадрати, както и произведението от тях.
На нечетни степени са вдигнати четните числа 2,4,6...
Нека ги представим като 2*2^98, 4*4^96 ... 98*98^2, 100. Четните степени са си точни квадрати.
остава 2*4*6*...*98*100, което е 2^50*50!
2^50 e точен квадрат. Остава да махнем 50!