Разминка для ума

[Hottabych]

Найти натуральное число, которое при делении на 9, 16 и 25 дает в остатке 2, 6 и 11 соответственно.

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

[Biotech]

Написать простенькую программку и зарядить в конпутер. Пусть он думает, у него мозгов много

[Old_Pepper]

...а хотя бы намекните, в каком направлении двигаться

Эх я б тебе намекнууууул бы.
Вместо того, чтоб работу работать, сижу "мозг разминаю".
А он не разминается.

[Hottabych]

Нет, эта задача совершенно точно имеет аналитическое решение, принципиально не хочу прибегать к прямому перебору, так как для программирования задачка просто элементарная .

[naryv]

2486

[mr_tank]

ну а теперь хотелось бы узнать, как получили данное число, и как выглядит элемиентарно переборное решение из утверждения хоттабыча.

[Hottabych]

переборное решение выглядит очень просто (см. приложенный файл с алгоритмом).

[Hottabych]

На самом деле, начинаться цикл должен с числа 36, просто печатал на скорую руку.

2Naryv:
выкладки в студию!

[POP]

На самом деле, начинаться цикл должен с числа 36, просто печатал на скорую руку.

Да, цикл должен начинаться с 36 и быть с шагом 25 (меньше перебирать)

2Naryv:
выкладки в студию!

Решил эту задачку почти без перебора (на признаках деления).
Решение сегодня выложу.
Сейчас нужно маленько поработать. (начальство пристаёт, противное) .

[POP]

Вот решение

Условия
№1 число при делении на 9 даёт остаток 2,
№2 число при делении на 16 даёт остаток 6
№3 число при делении на 25 даёт остаток 11


Искомое число без 11 делится на 25(а значит и на 5). Признак деления на 5: последняя цифра 5 или 0 => последняя цифра искомого числа 6 или 1
Последняя цифра не может быть 1, т.к. искомое число – чётное (при делении на чётное число (16) даёт чётный остаток (6)).
Значит искомое число имеет вид х…х6.
Искомое число без 11 имеет вид х…х5, значит частное от его деления на 25 – не чётное (иначе последнюю цифру получим 0). Следовательно, вторая цифра (числа без 11) может быть 2 или 7, а вторая цифра искомого числа 3 или 8.
Из условия №2 число х…хх0 (хххх6-6) делится на 16, значит частное от деления числа ххх0 на 2 – чётное. Это может быть только если вторая цифра чётная (иначе получим на конце частного от делния на 2 пятёрку)
Значит , искомое число имеет вид хххх86.

По условию №2, число ххх80(ххх86-6) должно делиться на 16 => последняя цифра частного от деления числа ххх80 на 16 может быть только 5 (иначе не получим 0 на конце), т.е имеет вид ууу5, вторая цифра этого числа может быть либо 0 либо 5 (иначе не получим 8 на второй позиции искомого числа)
Частное от деления числа имеет вид 50*n+5.
Искомое число без 6 имеет вид ххх80=16*(50n+5)=16*50n+80, т.е. хххх00= 16*50n =>
ххх0=16*5n.

Теперь вспомним признак деления на 9 (сумма цифр числа должна делиться на 9)
Т.е. из условия №3 в числе вида ххх86-2=ххх84, сумма цифр должна делиться на 9.
Сумма последних двух нам известна (12) => сумма всех предыдущих цифр имеет вид 6+9*m. (6 или 15 или24….).
Получилось условие №4.

Дальше без перебора по n обойтись не удалось.
При n=1
16*5n=80
Сумма цифр 8 – не удовлетворяет условию №4

При n=2
16*5n=160
Сумма цифр 7 – не удовлетворяет условию №4

При n=3
16*n=240
Сумма цифр удовлетворяет условию №4
Искомое число
2486

[naryv]

Во! Сразу видно, POP - голова! Только можно было-бы подождать, с выкладыванием выкладок( каламбурчикс) - чтоб другие поразмяли

а алгоритм Hottabych-а можно ускорить весьма
цикл по i=1 до бесконечности с шагом 1
если остаток(25*i +5)/16 = 0 то
если остаток(25*i + 9)/9 = 0 то
решение найдено
вывод (25*i +11)

[Hottabych]

POP:
Спасибо! Решение получилось очень остроумное. Я-то, дурак, пытался втупую решить через систему из 3х уравнений с четырьмя неизвестными... Интуиция, конечно, подсказывала, что неспроста там 9, 16, 25 (3^2, 4^2, 5^2), но теперь всё встает на свои места! И замечательно подойдут признаки деления на 3, 4, 5.

[Любитель]

Гы, а я общую формулу нашел
X=144(17+25g)+38 , Где g пробегает натуральный ряд.
Если интересно, могу изложить решение(оно кстати основано на целочисленном решении уравнений), я обошелся только делимостью на пять и на два, ибо других признаков не помнил.

Догоним и перегоним попроизводителности ЭВМ!!!!!! :p :p

[POP]

POP:
Спасибо! Решение получилось очень остроумное. Я-то, дурак, пытался втупую решить через систему из 3х уравнений с четырьмя неизвестными... Интуиция, конечно, подсказывала, что неспроста там 9, 16, 25 (3^2, 4^2, 5^2), но теперь всё встает на свои места! И замечательно подойдут признаки деления на 3, 4, 5.

В моём решении есть ошибка (правда результат правильный).
Кто нашёл?

[POP]

Гы, а я общую формулу нашел
X=144(17+25g)+38 , Где g пробегает натуральный ряд.
Если интересно, могу изложить решение(оно кстати основано на целочисленном решении уравнений), я обошелся только делимостью на пять и на два, ибо других признаков не помнил.

Догоним и перегоним попроизводителности ЭВМ!!!!!! :p :p

Выкладывай.

[GoRRik]

POP:
Спасибо! Решение получилось очень остроумное. Я-то, дурак, пытался втупую решить через систему из 3х уравнений с четырьмя неизвестными... Интуиция, конечно, подсказывала, что неспроста там 9, 16, 25 (3^2, 4^2, 5^2), но теперь всё встает на свои места! И замечательно подойдут признаки деления на 3, 4, 5.

Интересно. А вот если составить систему из 3-х линейных уравнений с 3-мя неизвестными и попробовать решить систему матричным способом, то у нас получится, что система имеет нетривиальное решение. Т.е. существует бесконечное множество решений данной задачи и натуральное число 2486 отнюдь не единственное решение Возьмите например число 6086 или 9686. Если ряд продолжить, то множество ответов для данной задачи будет представлять бесконечную последовательность в виде:

Pn=2486+3600*(n-1) ; где n E (1, 2, 3, .... , n)

; если внимательно посмотреть, то 3600=9*16*25

Для проверки можно разделить 23683286 на 9, 16 и 25 и получить те же остатки, что и при делении 2486

P.S. Извините что влез - неудержалси

[Любитель]

Выкладывай.

Пусть искомое число Y
Тогда имеем систему:
9a+2=Y
16b+6=Y
25c+11=y

Из первых двух получим 16b=9a-4(*) или 4b=9a/4-1. Пусть a0,b0; a,b-два решения, тогда (а-а0)9/16 =b-b0 (то есть приращение a должно быть кратно 16, методом пристального вглядывания в (*) определяем что a0=4, значит а=4(1+4X), где Х- натуральное число.
Теперь из всех возможных X-в, выберем удовлетворяющие третьему уравнению, а именно
25c=9а-9=36(1+4X)-9=144X-27, переписывая получим
25(с-1)=144Х+2 (**). рассуждая аналогично, получим что приращение решений для Х кратно 25.
Для нахождения первого занчения метод пристального вглядывания не сработал, по-этому начинаем шаманить.
Видно что число в правой части (**) два раза делится на 5 и без двойки оканчивается на четное число, это возможно если Х оканчивается на 7.
144*7=1008 Следующий разряд F надо выбрать так, чтобы 40*F+10 делилось на 25, получаем F=1. То есть 25с+11=144(17+25G)+38. Если бы F подобрать не удалось, пришлось бы рассматривать следующий разряд.

Примечательно, что 144=9*16, тоесть искомое чило =2486+9*16*25*g, что должно было быть очевидным с самого начала.

[naryv]

2 Boz то, что решение не единственное, это понятно из с.у. а вот последовательность интересная получилась
2 Любитель интересный способ, его я начал, до конца не прокрутил

[Hottabych]

Спасибо за участие! Думаю, мы все вынесли для себя кое-что новое. Я - прежде всего то, что никогда нельзя зацикливаться на стандартных методах (и забывать об этом). И вообще, предлагаю размещать тут интересные задачки из области математики (ну, и программирования ).

[Любитель]

В своем посте обнаружил опечатку (недопечатку), теперь все правильно.

[HT]

Старо, но очень мне нравится:

Соединить все точки между собой четырьмя прямыми, не отрывая карандаша от бумаги:

[Hottabych]

Ну это действительно просто.
И совсем не по математике

[HT]

Ну это действительно просто.
И совсем не по математике

Ээээ, да ты волшебной фразы не сказал...

[CoValent]

Старо, но очень мне нравится:

Соединить все точки между собой четырьмя прямыми, не отрывая карандаша от бумаги:

На психфаке это с осени 97-го года делают 3-мя прямыми линиями или 1-й не прямой - как только преподаватель забывает добавить "прямыми"...

[FilippOk]

Мне кажется, тремя - невозможно.