Дети и овцы

[Evgeniy Sklyarevskiy]

Жил-был пастух, и было у него в жизни две радости: разводить овец и растить детей.

Детей у него было 24, а овец — намного больше.
Когда денег совсем не осталось, поехал он на ярмарку и продал всех овец.
Вернувшись домой, он захотел разделить выручку поровну между своими детьми, но не тут-то было. Не делится, и все.
Пошел он к учёному соседу и стал жаловаться на несправедливую жизнь. Тот его и спрашивает: «А сколько же денег ты заработал?»
Пастух долго чесал в затылке: «Помню только, что количество овец было большим простым числом и продал я каждую овцу за столько монет, сколько первоначально было овец в стаде».
Ученый сосед в ответ: «Невелика беда, дай мне 1 монетку за совет, а остальные деньги дели себе на здоровье».
Обрадовался пастух, пришел домой и все сделал как сказано.
А потом стал думать: «Как мой ученый сосед смог узнать, что оставшиеся деньги можно поделить поровну?»

И в самом деле, как?

[Shuhrat Ismailov]

Пусть p - простое число (p > 3), тогда по условию задачи он заработал денег (за вычетом премии соседу)
p^2-1 = (p + 1)(p − 1)
Оно обязательно делится на 24 при p>3.
Докажем это .
Для этого посмотрим на что делится число (p + 1)(p − 1).
1) Поскольку p — простое, то среди делящихся на 2 его не будет, а среди трех последовательных чисел p − 1, p, p + 1, одно обязательно делится на 2, но это не p. Значит, одно из чисел p + 1 или p − 1 (а следовательно и произведение (p + 1)(p − 1)) делится на 2.
2) Аналогично доказывается делимость (p + 1)(p − 1) на 3 .
3) Докажем делимость на 4. Рассмотрим числа p − 1, p, p + 1, p + 2.
Из четырех последовательных чисел одно обязательно делится на 4, но это не p (оно простое) и не p + 2 (оно нечетное).
Значит, одно из чисел p + 1 или p − 1 (а следовательно и произведение (p + 1)(p − 1)) будет делиться на 4.
Окончательно имеем, что одно из чисел p + 1 или p − 1 делится на 2, на 3, на 4, значит произведение (p + 1)(p − 1) делится на 2, на 3, на 4, то есть оно делится на произведение 2х3х4=24.

[Nadir Zaitov]

Значит, одно из чисел p + 1 или p − 1 (а следовательно и произведение (p + 1)(p − 1)) будет делиться на 4. Окончательно имеем, что одно из чисел p + 1 или p − 1 делится на 2, на 3, на 4, значит произведение (p + 1)(p − 1) делится на 2, на 3, на 4, то есть оно делится на произведение 2х3х4=24. 4-число составное. Лучше сначала заметить, что и p-1 и p+1 делятся на 2 и хотя бы одно из них делится на 4. Тогда все получится. А так, спасибо за решение.

[Шура Балаганов]

1) Поскольку p — простое, то среди делящихся на 2 его не будет, а среди трех последовательных чисел p − 1, p, p + 1, одно обязательно делится на 2, но это не p. Значит, одно из чисел p + 1 или p − 1 (а следовательно и произведение (p + 1)(p − 1)) делится на 2.
Вообще-то, усложняете. Если р - нечетное число, то в любом случае соседние с ним числа четные, без всяких рассуждений про три последовательных числа. И говорить "одно из чисел р+1 или р-1 делится на 2" - грубая ошибка. Они оба четные

[Nadir Zaitov]

Вообще-то, усложняете. Если р - нечетное число, то в любом случае соседние с ним числа четные, без всяких рассуждений про три последовательных числа. И говорить "одно из чисел р+1 или р-1 делится на 2" - грубая ошибка. Они оба четные А я первый заметил, а я первый... Тут грубых ошибок вообще не бывает. Тут мнения. Если есть что дополнить - так и пишите. Не надо правоцировать оффтоп и холивар. В слудующий раз выставлю штраф как за неприемлемое поведение

[Наташа]

"одно из чисел р+1 или р-1 делится на 2" - грубая ошибка. Они оба четные То, что они оба четные -ведь ни как не отменяет того, что одно из этих 2х чисел делиться на 2...:) -как Вы считаете?...:)

[Nadir Zaitov]

То, что они оба четные -ведь ни как не отменяет того, что одно из этих 2х чисел делиться на 2... -как Вы считаете?... Боюсь я Балаганова спугнул основательно. Он всех модеров, кроме меня, закидал жалобами :)Шура Балаганов не понял в чем реальная неаккуратность в доказательстве тески, которую я как раз предыдущим постом отметил.

Если известно, что А или Б делятся на 2, 3, 4, то это не значит, что их произведение, делится на 2*3*4, так как А может делиться и на 2 и на 4 одновременно, но не на 8, а Б не делиться на 2 вообще: А=4, Б=3 и т.п.

Т.е. замечание, что А и Б четные помогало, но это не делало неверным конкретные выражения Шухрата, что хотя бы А или Б четно! Оно остается истинным и не может быть "грубой ошибкой".

Подобные откровенно делитантские замечания, я уверен, неприятны были бы всем, в том числе мне, с чем и было связано предупреждение. Тем более, что само доказательство красиво, лаконично и принципиально правильное.

[Shuhrat Ismailov]

Шура Балаганов не понял в чем реальная неаккуратность в доказательстве тески.
Спасибо Надир! Напомнил студенческие годы. Меня сейчас только мама Шуриком зовет (жена удивляется).

[Evgeniy Sklyarevskiy]

Интересное развитие задачи: А если бы сосед сказал: «Дай мне 4 (9, 16, 25... N^2 монет) делилось ли оставшееся число на 24?

[Evgeniy Sklyarevskiy]

Иначе говоря найти, при каких k=2,...,N возможна делимость числа k^2-1 на 24.
Ясно, что при любом простом k число k^2-1 на 24 делится.
Значит, если отдать соседу простое число монет, то все сойдется!!!

[Shuhrat Ismailov]

Интересное развитие задачи: А если бы сосед сказал: «Дай мне 4 (9, 16, 25... N^2 монет) делилось ли оставшееся число на 24?
Сейчас требуется исследовать, при каких k=2,...,N возможна делимость числа
p^2-k^2 на 24.
Так как p^2-k^2=(p^2-1)-(k^2-1), причем по доказанному выше p^2-1 делится на 24, то делимость числа p^2-k^2 на 24 равносильна делимости k^2-1 на 24.
Поэтому задача Скляревского получает следующую модификацию:
"Жил-был пастух, и было у него в жизни две радости: разводить овец и растить детей.
Детей у него было 24, а овец — намного больше.
Когда денег совсем не осталось, поехал он на ярмарку и продал всех овец.
Вернувшись домой, он захотел разделить выручку поровну между своими детьми, но не тут-то было. Не делится, и все.
Пошел он к учёному соседу и стал жаловаться на несправедливую жизнь. Тот его и спрашивает: «А сколько же денег ты заработал?»
Пастух долго чесал в затылке: «Помню только, что количество овец было большим простым числом и продал я каждую овцу за столько монет, сколько первоначально было овец в стаде».
Ученый сосед в ответ: «Невелика беда, дай мне 1 монетку за совет, а остальные деньги дели себе на здоровье»."
Возможно ли такое?
Иначе говоря найти, при каких k=2,...,N возможна делимость числа k^2-1 на 24.
Ясно, что при любом простом k число k^2-1 на 24 делится.
А при k=24 число k^2-1 на 24 не делится.
Не надо ему давать больше одной монетки, не заслужил.

[Shuhrat Ismailov]

Значит, если отдать соседу простое число монет, то все сойдется!!!
Вернее, квадрат простого числа.

[Nadir Zaitov]

Значит, если отдать соседу простое число монет, то все сойдется!!! Судя по доказательству достаточно и вполне может быть необходимо, чтобы N было нечетным и не делилось на 3.

[Shuhrat Ismailov]

Судя по доказательству достаточно и вполне может быть необходимо, чтобы N было нечетным и не делилось на 3.
Согласен, что в этом случае k^2-1 делится на 24.
Если k=2,3,....,N нечетно и не делится на 3, то оно взаимно просто с 24.
А как быть с необходимостью?
Скорее всего, это следует из следующего факта.
k^2-1 делится на 24 тогда и только тогда, когда
одновременно k^2-1 делится на 8 и k^2-1 делится на 3.

[Nadir Zaitov]

А как быть с необходимостью? Скорее всего, это следует из следующего факта. Ага. Я тоже так подумал.