ММ, 8 тур. Тематический конкурс "Арифметика"
По адресу http://www.fizmat.vspu.ru:8000/doku.php?id=marathon:about начался восьмой тур "Математического марафона", проводимого Владимиром Лецко.
В рамках тура проводится тематический конкурс "Арифметика", состоящий из 5 задач.
По традиции, создаю у себя посты, в которых буду выкладывать свои решения задач по мере открытия ответов на них. Этот пост будет посвящен задачам тематического конкурса.
Задачам 8 тура, не входящим в тематический конкурс посвящен отдельный пост: http://fiviol.livejournal.com/33273.html
Помимо прочего, этот пост служит рекламой марафона. Присоединяйтесь! Решения можно посылать по адресу, указанному по приведенной выше ссылке.
ММ-7. Задачи, не входящие в тематический конкурс.
http://fiviol.livejournal.com/24291.html
ММ-7. Задачи тематического конкурса "Логика"
http://fiviol.livejournal.com/23124.html
ММ-6. Задачи 56-60.
http://fiviol.livejournal.com/17825.html
ММ-6. Задачи 51-55.
http://fiviol.livejournal.com/14750.html
Конкурсная задача №71 (А-1) (4 балла)
Назовем n-значное натуральное число "замечательным", если оно равно сумме n-х степеней своих цифр. Конечно ли множество замечательных чисел?
Пpимечание: система счисления десятичная.
Ответ: Это множество конечно.
Решение: Минимальным n-значным числом является 10^(n-1), максимальной суммой n-x степеней цифр n-значного числа является n*9^n. Таким образом, количество цифр замечательного числа заведомо должно удовлетворять неравенству n*9^n >= 10^(n-1), или 10n >= (10/9)^n. Поскольку показательная функция растет быстрее линейной, это неравенство перестает выполняться, начиная с некоторого n = N. Значит, замечательные числа имеют не больше N-1 знака, то есть их конечное число.
Моя эстетическая оценка задачи - 2 балла. 12.06.07.
За правильное решение этой задачи Константин Кноп и Влад Франк получают по 5 призовых баллов. Они (разными путями) получили полный список замечательных чисел. Сергей Аракчеев, Сергей Беляев, Дмитрий Бобровский, Андрей Богданов, Иван Козначеев, Алекс Кочарин, Евгений Машеров, Дмитрий Милосердов, Олег Полубасов, Виктор Филимоненков получают по 4 призовых балла. За некоторые соображения по решению Стас Грицюк получает 1 призовой балл.
Конкурсная задача №73 (А-2) (6 баллов)
а) A - множество из пяти натуральных чисел. Множество B состоит из сумм элементов всевозможных подмножеств множества A, при условии, что эти суммы простые числа. Каково наибольшее возможное число элементов B?
б) Для решения вышеизложенной задачи Вася написал программу. Эта программа обнуляет счетчик и (псевдо)случайным образом генерирует массив из пяти натуральных чисел. Затем перебираются (по одному разу) всевозможные суммы элементов этого массива (по одному, по два, по три, по четыре, по пять). Всякий раз, когда сумма является простым числом, счетчик увеличивается на единицу. Какое наибольшее значение счетчика может вернуть Васина программа?
Ответы. а) 17, б) 21.
Решение. а) При A = {2; 6; 101; 1380; 1770} множество В состоит из 17 элементов: 2 и четыре четверки простых вида k, k+2, k+6, k+8. В = {2; 101; 103; 107; 109; 1481; 1483; 1487; 1489; 1871; 1873; 1877; 1879; 3251; 3253; 3257; 3259}.
Покажем, что больше элементов в В быть не может. Если в А пять четных, то в В все числа четные, а, значит, возможно максимум одно простое. Если в А есть хотя бы одно нечетное число x, то все подмножества элементов из А разобьем на пары: каждому из 2^4 = 16 подмножеств, не содержащих x, в пару поставим это же подмножество с добавленным к нему элементом x. Поскольку четности сумм элементов в подмножествах каждой такой пары различны, среди элементов В максимум 16 нечетных, значит, максимум 17 простых (если число 2 входит в А и, значит, в В).
б) Если будет сгенерирован массив состоящий из пяти единиц, то счетчик увеличится 10 раз для каждой суммы двух элементов, 10 раз для каждой суммы трех элементов, и 1 раз для суммы всех пяти элементов, всего вернув значение 21.
Покажем, что больше 21 счетчик вернуть не может. Рассмотрим все возможные случаи количеств в сгенерированном массиве четных (Ч), нечетных (Н) чисел и, отдельно, единиц (1). В каждом таком случае посчитаем максимально возможное (точнее, оценку сверху) количеств простых сумм (учитывая, что 1 простым числом не является, а кроме 2 других четных простых нет):
11111: 0+10+10+0+1 = 21 (слагаемые означают возможные количества простых, являющихся суммами соответственно 1, 2, 3, 4, 5 элементов).
1111Ч: 1+10+4+4+0 = 19
1111Н: 1+6+10+0+1 = 18
111ЧЧ: 2+9+4+2+1 = 18
111ЧН: 2+7+4+4+0 = 17
111НН: 2+3+10+0+1 = 16
11ЧЧЧ: 1+7+6+2+0 = 18
11ЧЧН: 3+7+4+2+1 = 17
11ЧНН: 3+5+4+4+0 = 16
11ННН: 3+1+10+0+1 = 15
1ЧЧЧЧ: 4+4+6+4+1 = 19
1ЧЧЧН: 4+6+6+2+0 = 18
1ЧЧНН: 4+6+4+2+1 = 17
1ЧННН: 4+4+4+4+0 = 16
1НННН: 4+0+10+0+1 = 15
ЧЧЧЧЧ: 5+0+0+0+0 = 5
ЧЧЧЧН: 5+4+6+4+1 = 20
ЧЧЧНН: 5+6+6+2+0 = 19
ЧЧННН: 5+6+4+2+1 = 18
ЧНННН: 5+4+4+4+0 = 17
ННННН: 5+0+10+0+1 = 16
Видно, что больше 21 простой суммы быть не может.
Моя эстетическая оценка - 5 баллов (особенно за пункт а). 18.06.07.
Владислав Франк, правильно решивший и обобщивший эту задачу, получает 8 призовых баллов. За правильное решение Андрей Богданов, Дмитрий Милосердов, Олег Полубасов и Виктор Филимоненков получают по 6 призовых баллов. За правильное решение с некоторыми шероховатостями Сергей Беляев и Константин Кноп получают по 5 призовых баллов. За правильное, но неполное решение Анатолий Казмерчук получает 4 балла.
Конкурсная задача №75 (А-3) (8 баллов)
Для каждого натурального q, большего 1, опрелелим функцию натурального аргумента Jq(n) следующим образом:
Расставим натуральные числа от 1 до n по кругу. Пропускаем 1 и вычеркиваем числа 2,... q. Пропускаем число q+1 и вычеркиваем следующие q-1 чисел. И так далее. До тех пор, пока не останется всего одно число. Оно-то и будет значением Jq(n).
1. Для каждого q описать все n, для которых Jq(n) = n.
2. Найти явную формулу для J3(n).
Ответ: 1. Для n = t*q^s-q+1, где s - любое натуральное, t < q.
2. Запишем число n в виде n = r*3^s+2*l, где r = 2 минус остаток от деления n на 2, s - наибольшее неотрицательное целое такое, что r*3^s не превосходит n, (тогда l - неотрицательное целое от 0 до r*3^s-1). Тогда J3(r*3^s+2*l) = 1+3*l.
Решение.
1. Чтобы число n осталось не вычеркнутым на первом круге, оно должно иметь вид n = q*k+1. После первого круга останется k+1 число, и чтобы n осталось не вычеркнутым после второго круга, нужно чтобы k+1 делилось на q: k+1 = q*l, то есть n = q(q*l-1)+1. После второго круга останется l чисел. Значит, l тоже должно делиться на q, и так далее, пока после очередного круга не останется меньше q чисел - тогда n будет наверняка вычеркнуто последним. То есть n = q*(t*q^(s-1)-1)+1, где s - количество кругов.
2. Пройдя один круг и рассмотрев, сколько останется не вычеркнутых чисел, получим рекурсивные формулы (индекс 3 для функции J(n) я везде опускаю):
J(3k)=3J(k)-2;
J(3k+1) = 3J(k-1)+4;
J(3k+2) = 3J(k)+1.
Докажем теперь приведенную в ответе явную формулу для J(n) по индукции. Верность формулы при малых n проверяется непосредственно:
J(1) = J(1*3^0+2*0) = 1+3*0 =1 - верно,
J(2) = J(2*3^0+2*0) = 1+3*0 = 1 - верно,
J(3) = J(1*3^1+2*0) = 1+3*0 = 1 - верно,
J(4) = J(2*3^0+2*1) = 1+3*1 = 4 - верно, и т.д.
Пусть формула верна для всех целых чисел, меньших r*3^s+2*l. Покажем, что формула верна и для n = r*3^s+2*l Рассмотрим три случая различных остатков от деления l на 3. Используя рекурсивные формулы, получим:
J(r*3^s+2*(3k)) = (по рекурсивной формуле) = 3J(r*3^(s-1)+2*k)-2 = (по предположению индукции) = 3*(3k+1)-2 = 3*l+1.
J(r*3^s+2*(3k+1)) = J(r*3^s+2*(3k)+2) = (по рекурсивной формуле) = 3J(r*3^(s-1)+2*k)+1 = (по предположению индукции) = 3*(3k+1)+1 = 3*l+1.
J(r*3^s+2*(3k+2)) = J(r*3^s+3*(2*k+1)+1) (по рекурсивной формуле) = 3J(r*3^(s-1)+(2*k+1)-1)+4 = (по предположению индукции) = 3*(3k+1)+4 = 3*(3k+2)+1 = 3*l+1.
Во всех трех случаях формула выполняется.
Моя эстетическая оценка задачи: 5 баллов. 5.09.07.
За верное решение задачи и обобщение второго пункта на любое q Анатолий Казмерчук и Олег Полубасов получают по 9 призовых баллов. За правильное решение здачи Константин Кноп и Виктор Филимоненков получают по 8 призовых баллов. Влад Франк, решивший только первый пункт, получает 3 призовых балла.
Конкурсная задача №77 (А-4) (8 баллов)
Каждое из n натуральных чисел, идущих подряд, имеет ровно k натуральных делителей. Какое наибольшее значение может принимать n, если:
1) k = 2; 2) k = 3; 3) k = 4; 4) k = 6; 5) k = 8?
Ответы. 1) 2. 2) 1. 3) 3. 4) верхняя оценка 5, предполагаю, что это точная оценка. 5) верхняя оценка 7, предполагаю, что это точная оценка.
Решение: Общее замечание. Пусть p1^a1*...*ps^as - каноническое разложение числа в произведение простых множителей. Его делителями являются числа вида p1^x1*...*ps^xs, где хi независимо друг от друга могут принимать значения от 0 до ai. Значит, такое число имеет (a1+1)*...*(as+1) делителей.
1) В силу общего замечания, k = 2 делителя у числа может быть, только если оно является первой степенью простого, то есть простым числом. Максимум возможно 2 подряд простых числа: 2 и 3.
2) k = 3 будет у чисел вида p^2 (p простое). Ясно, что два подряд квадрата натуральных чисел не существует.
3) Поскольку 4 можно разложить двумя способами в произведение множителей: 4 и 2*2, то k = 4 делителя есть у чисел вида p^3 или p*q (p, q простые). Три подряд числа такого вида легко найти, например, 33 = 3*11, 34 = 2*17, 35 = 5*7. Четыре подряд числа такого вида быть не может, так как среди таких чисел хотя бы одно делится на 2^2, а значит должно быть равно 2^3. Но простая проверка показывает, что никакая четверка подряд идущих чисел, одно из которых 8, не имеет по 4 делителя.
4) Поскольку 6 двумя способами раскладывается в произведение: 6 и 2, в силу общего замечания, по 6 делителей имеют числа вида p^5 и p^2*q, (p, q простые). Покажем, что больше пяти подряд идущих таких чисел быть не может. Действительно, из 6 подряд идущих чисел есть 3 четных числа. Если среди трех подряд идущих четных чисел два делятся на 4, то одно из этих четных чисел делится на 2^3. Тогда оно должно быть равно 2^5, но проверка показывает, что соседние с 32 числами не имеют по 6 делителей. Если же среди трех подряд идущих четных чисел только одно делится на 4, то два других числа, отличающиеся на 4, должны иметь вид 2*p^2, где p нечетное простое. Но квадраты нечетных чисел не могут отличаться на 2.
Найти пятерку подряд идущих чисел с 6 делителями я не сумел, хотя я не вижу причин, почему бы такой пятерке не существовать. Четыре подряд идущих числа с шестью делителями: 242 = 2*11^2, 243 = 3^5, 244 = 2^2*61, 245 = 5^2*49.
5) Поскольку 8 тремя способами раскладывается в произведение множителей: 8, 4*2 и 2*2*2, то по 8 делителей имеют числа вида p^7, p^3*q и p*q*r (p, q, r - простые). Покажем, что больше 7 подряд идущих таких чисел быть не может. Действительно, из 8 подряд идущих чисел одно делится на 2^2, но не делится на 2^3, но такое число не может иметь 8 делителей.
Найти семерку подряд идущих таких чисел (и даже четверку) я оказался неспособен. Однако тоже не вижу причин, почему бы такой семерке не быть.
Эстетическая оценка: как всегда, с нерешенной задачей проблемы. Первые три пункта слишком просты и поэтому неинтересны. А у оставшихся двух я не знаю решения, думаю, что нужен компьютерный перебор. Тем не менее, моя эстетическая оценка - 4 балла. Всегда здорово, что за таким простым по формулировке вопросом оказывается нетривиальная задача. 12.10.07.
За верное решение задачи и ее обобщение Влад Франк получает 11 призовых баллов. За правильное решение задачи Константин Кноп и Анатолий Казмерчук получают по 8 призовых баллов. За верные, но неполные (в разной степени) решения: Олег Полубасов получает 7 призовых баллов; Виктор Филимоненков - 6 баллов; Галина Крюкова - 5 баллов.
Конкурсная задача №79 (А-5) (6 баллов)
Сколько решений имеет нижеприведенная система уравнений?
[x] + {y} = [y]*{x}; x + y = n
Примечания: [x] = floor(x) - целая часть (пол) x; {x} = frac(x) - дробная часть x; n - целочисленый параметр.
Ответ: Бесконечно много решений при n = -1; [n/2] + 1 решение при n >= 0; [|n/2|] решений при n <= -2.
Решение. Случай 1. Если {x} = 0. Тогда из второго уравнения следует, что и {y} = 0, тогда из первого следует, что [x] = 0, то есть x = 0, откуда y = n. То есть при любом n есть одно целочисленное решение.
Случай 2. Пусть x (а значит и y) не являются целыми. Тогда {y} = 1 - {x}, а из второго уравнения следует, что [y] = n - [x] - 1. Подставляя эти выражения в первое уравнения, получим: [x] + 1 - {x} = (n - [x] - 1)*{x}, то есть
n = ([x] + 1)/{x} + [x] (*)
или {x} = ([x] + 1)/(n - [x]) (**)
Каждое решение x этих уравнений дает решение (x,y) исходной системы, поэтому будем решать (*).
При n = -1 равенство (*) выполняется для любого x, при котором [x] = -1. Таким образом, решений в этом случае бесконечно много (континуум).
При n >= 0 равенство (*) выполняется только при [x] >= 0. Поскольку, однако, 0 < {x} < 1, то из (*) следует, что n > 2[x]+1, то есть 0 <= [x] < (n-1)/2. Значит, [x] может принимать [n/2] значений. {x} при каждом таком значении выражается из (**), то есть существует [n/2] + 1 решение системы (с учетом решения из случая 1)
При n <= -2 равенство (*) может выполняться только при [x] <=-2. Поскольку {x} все так же меньше 1, то из (*) следует, что n < 2[x]+1, то есть (n-1)/2 < [x] <= -2. Это дает [|n/2|] - 1 возможное значение [x], по каждому из которых {x} восстанавливается из (**). Значит, с учетом решения из случая 1, имеется [|n/2|] решений системы.
Эстетическая оценка задачи: 3 балла. 24.10.07.
За правильное решение этой задачи Виктор Филимоненков и Анатолий Казмерчук получают по 6 призовых баллов. За верные по сути, но не лишенные неточностей решения: Владислав Франк получает 5 призовых баллов, Константин кноп, Галина Крюкова и Олег Полубасов - по 4 призовых балла, Ефим Подвойский - 3 призовых балла.
Итоги мини-конкурса арифметических задач
1. Владислав Фpанк 32
2. Анатолий Казмерчук 31
3. Виктоp Филимоненков 30
3. Олег Полубасов 30
3. Константин Кноп 30
6. Дмитpий Милосеpдов 10
7. Андpей Богданов 10
8. Сергей Беляев 9
8. Галина Крюкова 9
10. Евгений Машеpов 4
10. Иван Козначеев 4
10. Алекс Кочаpин 4
10. Дмитрий Бобровский 4
10. Сеpгей Аpакчеев 4
15. Ефим Подвойский 3
16. Стас Гpицюк 1
В рамках тура проводится тематический конкурс "Арифметика", состоящий из 5 задач.
По традиции, создаю у себя посты, в которых буду выкладывать свои решения задач по мере открытия ответов на них. Этот пост будет посвящен задачам тематического конкурса.
Задачам 8 тура, не входящим в тематический конкурс посвящен отдельный пост: http://fiviol.livejournal.com/33273.html
Помимо прочего, этот пост служит рекламой марафона. Присоединяйтесь! Решения можно посылать по адресу, указанному по приведенной выше ссылке.
ММ-7. Задачи, не входящие в тематический конкурс.
http://fiviol.livejournal.com/24291.html
ММ-7. Задачи тематического конкурса "Логика"
http://fiviol.livejournal.com/23124.html
ММ-6. Задачи 56-60.
http://fiviol.livejournal.com/17825.html
ММ-6. Задачи 51-55.
http://fiviol.livejournal.com/14750.html
Конкурсная задача №71 (А-1) (4 балла)
Назовем n-значное натуральное число "замечательным", если оно равно сумме n-х степеней своих цифр. Конечно ли множество замечательных чисел?
Пpимечание: система счисления десятичная.
Ответ: Это множество конечно.
Решение: Минимальным n-значным числом является 10^(n-1), максимальной суммой n-x степеней цифр n-значного числа является n*9^n. Таким образом, количество цифр замечательного числа заведомо должно удовлетворять неравенству n*9^n >= 10^(n-1), или 10n >= (10/9)^n. Поскольку показательная функция растет быстрее линейной, это неравенство перестает выполняться, начиная с некоторого n = N. Значит, замечательные числа имеют не больше N-1 знака, то есть их конечное число.
Моя эстетическая оценка задачи - 2 балла. 12.06.07.
За правильное решение этой задачи Константин Кноп и Влад Франк получают по 5 призовых баллов. Они (разными путями) получили полный список замечательных чисел. Сергей Аракчеев, Сергей Беляев, Дмитрий Бобровский, Андрей Богданов, Иван Козначеев, Алекс Кочарин, Евгений Машеров, Дмитрий Милосердов, Олег Полубасов, Виктор Филимоненков получают по 4 призовых балла. За некоторые соображения по решению Стас Грицюк получает 1 призовой балл.
Конкурсная задача №73 (А-2) (6 баллов)
а) A - множество из пяти натуральных чисел. Множество B состоит из сумм элементов всевозможных подмножеств множества A, при условии, что эти суммы простые числа. Каково наибольшее возможное число элементов B?
б) Для решения вышеизложенной задачи Вася написал программу. Эта программа обнуляет счетчик и (псевдо)случайным образом генерирует массив из пяти натуральных чисел. Затем перебираются (по одному разу) всевозможные суммы элементов этого массива (по одному, по два, по три, по четыре, по пять). Всякий раз, когда сумма является простым числом, счетчик увеличивается на единицу. Какое наибольшее значение счетчика может вернуть Васина программа?
Ответы. а) 17, б) 21.
Решение. а) При A = {2; 6; 101; 1380; 1770} множество В состоит из 17 элементов: 2 и четыре четверки простых вида k, k+2, k+6, k+8. В = {2; 101; 103; 107; 109; 1481; 1483; 1487; 1489; 1871; 1873; 1877; 1879; 3251; 3253; 3257; 3259}.
Покажем, что больше элементов в В быть не может. Если в А пять четных, то в В все числа четные, а, значит, возможно максимум одно простое. Если в А есть хотя бы одно нечетное число x, то все подмножества элементов из А разобьем на пары: каждому из 2^4 = 16 подмножеств, не содержащих x, в пару поставим это же подмножество с добавленным к нему элементом x. Поскольку четности сумм элементов в подмножествах каждой такой пары различны, среди элементов В максимум 16 нечетных, значит, максимум 17 простых (если число 2 входит в А и, значит, в В).
б) Если будет сгенерирован массив состоящий из пяти единиц, то счетчик увеличится 10 раз для каждой суммы двух элементов, 10 раз для каждой суммы трех элементов, и 1 раз для суммы всех пяти элементов, всего вернув значение 21.
Покажем, что больше 21 счетчик вернуть не может. Рассмотрим все возможные случаи количеств в сгенерированном массиве четных (Ч), нечетных (Н) чисел и, отдельно, единиц (1). В каждом таком случае посчитаем максимально возможное (точнее, оценку сверху) количеств простых сумм (учитывая, что 1 простым числом не является, а кроме 2 других четных простых нет):
11111: 0+10+10+0+1 = 21 (слагаемые означают возможные количества простых, являющихся суммами соответственно 1, 2, 3, 4, 5 элементов).
1111Ч: 1+10+4+4+0 = 19
1111Н: 1+6+10+0+1 = 18
111ЧЧ: 2+9+4+2+1 = 18
111ЧН: 2+7+4+4+0 = 17
111НН: 2+3+10+0+1 = 16
11ЧЧЧ: 1+7+6+2+0 = 18
11ЧЧН: 3+7+4+2+1 = 17
11ЧНН: 3+5+4+4+0 = 16
11ННН: 3+1+10+0+1 = 15
1ЧЧЧЧ: 4+4+6+4+1 = 19
1ЧЧЧН: 4+6+6+2+0 = 18
1ЧЧНН: 4+6+4+2+1 = 17
1ЧННН: 4+4+4+4+0 = 16
1НННН: 4+0+10+0+1 = 15
ЧЧЧЧЧ: 5+0+0+0+0 = 5
ЧЧЧЧН: 5+4+6+4+1 = 20
ЧЧЧНН: 5+6+6+2+0 = 19
ЧЧННН: 5+6+4+2+1 = 18
ЧНННН: 5+4+4+4+0 = 17
ННННН: 5+0+10+0+1 = 16
Видно, что больше 21 простой суммы быть не может.
Моя эстетическая оценка - 5 баллов (особенно за пункт а). 18.06.07.
Владислав Франк, правильно решивший и обобщивший эту задачу, получает 8 призовых баллов. За правильное решение Андрей Богданов, Дмитрий Милосердов, Олег Полубасов и Виктор Филимоненков получают по 6 призовых баллов. За правильное решение с некоторыми шероховатостями Сергей Беляев и Константин Кноп получают по 5 призовых баллов. За правильное, но неполное решение Анатолий Казмерчук получает 4 балла.
Конкурсная задача №75 (А-3) (8 баллов)
Для каждого натурального q, большего 1, опрелелим функцию натурального аргумента Jq(n) следующим образом:
Расставим натуральные числа от 1 до n по кругу. Пропускаем 1 и вычеркиваем числа 2,... q. Пропускаем число q+1 и вычеркиваем следующие q-1 чисел. И так далее. До тех пор, пока не останется всего одно число. Оно-то и будет значением Jq(n).
1. Для каждого q описать все n, для которых Jq(n) = n.
2. Найти явную формулу для J3(n).
Ответ: 1. Для n = t*q^s-q+1, где s - любое натуральное, t < q.
2. Запишем число n в виде n = r*3^s+2*l, где r = 2 минус остаток от деления n на 2, s - наибольшее неотрицательное целое такое, что r*3^s не превосходит n, (тогда l - неотрицательное целое от 0 до r*3^s-1). Тогда J3(r*3^s+2*l) = 1+3*l.
Решение.
1. Чтобы число n осталось не вычеркнутым на первом круге, оно должно иметь вид n = q*k+1. После первого круга останется k+1 число, и чтобы n осталось не вычеркнутым после второго круга, нужно чтобы k+1 делилось на q: k+1 = q*l, то есть n = q(q*l-1)+1. После второго круга останется l чисел. Значит, l тоже должно делиться на q, и так далее, пока после очередного круга не останется меньше q чисел - тогда n будет наверняка вычеркнуто последним. То есть n = q*(t*q^(s-1)-1)+1, где s - количество кругов.
2. Пройдя один круг и рассмотрев, сколько останется не вычеркнутых чисел, получим рекурсивные формулы (индекс 3 для функции J(n) я везде опускаю):
J(3k)=3J(k)-2;
J(3k+1) = 3J(k-1)+4;
J(3k+2) = 3J(k)+1.
Докажем теперь приведенную в ответе явную формулу для J(n) по индукции. Верность формулы при малых n проверяется непосредственно:
J(1) = J(1*3^0+2*0) = 1+3*0 =1 - верно,
J(2) = J(2*3^0+2*0) = 1+3*0 = 1 - верно,
J(3) = J(1*3^1+2*0) = 1+3*0 = 1 - верно,
J(4) = J(2*3^0+2*1) = 1+3*1 = 4 - верно, и т.д.
Пусть формула верна для всех целых чисел, меньших r*3^s+2*l. Покажем, что формула верна и для n = r*3^s+2*l Рассмотрим три случая различных остатков от деления l на 3. Используя рекурсивные формулы, получим:
J(r*3^s+2*(3k)) = (по рекурсивной формуле) = 3J(r*3^(s-1)+2*k)-2 = (по предположению индукции) = 3*(3k+1)-2 = 3*l+1.
J(r*3^s+2*(3k+1)) = J(r*3^s+2*(3k)+2) = (по рекурсивной формуле) = 3J(r*3^(s-1)+2*k)+1 = (по предположению индукции) = 3*(3k+1)+1 = 3*l+1.
J(r*3^s+2*(3k+2)) = J(r*3^s+3*(2*k+1)+1) (по рекурсивной формуле) = 3J(r*3^(s-1)+(2*k+1)-1)+4 = (по предположению индукции) = 3*(3k+1)+4 = 3*(3k+2)+1 = 3*l+1.
Во всех трех случаях формула выполняется.
Моя эстетическая оценка задачи: 5 баллов. 5.09.07.
За верное решение задачи и обобщение второго пункта на любое q Анатолий Казмерчук и Олег Полубасов получают по 9 призовых баллов. За правильное решение здачи Константин Кноп и Виктор Филимоненков получают по 8 призовых баллов. Влад Франк, решивший только первый пункт, получает 3 призовых балла.
Конкурсная задача №77 (А-4) (8 баллов)
Каждое из n натуральных чисел, идущих подряд, имеет ровно k натуральных делителей. Какое наибольшее значение может принимать n, если:
1) k = 2; 2) k = 3; 3) k = 4; 4) k = 6; 5) k = 8?
Ответы. 1) 2. 2) 1. 3) 3. 4) верхняя оценка 5, предполагаю, что это точная оценка. 5) верхняя оценка 7, предполагаю, что это точная оценка.
Решение: Общее замечание. Пусть p1^a1*...*ps^as - каноническое разложение числа в произведение простых множителей. Его делителями являются числа вида p1^x1*...*ps^xs, где хi независимо друг от друга могут принимать значения от 0 до ai. Значит, такое число имеет (a1+1)*...*(as+1) делителей.
1) В силу общего замечания, k = 2 делителя у числа может быть, только если оно является первой степенью простого, то есть простым числом. Максимум возможно 2 подряд простых числа: 2 и 3.
2) k = 3 будет у чисел вида p^2 (p простое). Ясно, что два подряд квадрата натуральных чисел не существует.
3) Поскольку 4 можно разложить двумя способами в произведение множителей: 4 и 2*2, то k = 4 делителя есть у чисел вида p^3 или p*q (p, q простые). Три подряд числа такого вида легко найти, например, 33 = 3*11, 34 = 2*17, 35 = 5*7. Четыре подряд числа такого вида быть не может, так как среди таких чисел хотя бы одно делится на 2^2, а значит должно быть равно 2^3. Но простая проверка показывает, что никакая четверка подряд идущих чисел, одно из которых 8, не имеет по 4 делителя.
4) Поскольку 6 двумя способами раскладывается в произведение: 6 и 2, в силу общего замечания, по 6 делителей имеют числа вида p^5 и p^2*q, (p, q простые). Покажем, что больше пяти подряд идущих таких чисел быть не может. Действительно, из 6 подряд идущих чисел есть 3 четных числа. Если среди трех подряд идущих четных чисел два делятся на 4, то одно из этих четных чисел делится на 2^3. Тогда оно должно быть равно 2^5, но проверка показывает, что соседние с 32 числами не имеют по 6 делителей. Если же среди трех подряд идущих четных чисел только одно делится на 4, то два других числа, отличающиеся на 4, должны иметь вид 2*p^2, где p нечетное простое. Но квадраты нечетных чисел не могут отличаться на 2.
Найти пятерку подряд идущих чисел с 6 делителями я не сумел, хотя я не вижу причин, почему бы такой пятерке не существовать. Четыре подряд идущих числа с шестью делителями: 242 = 2*11^2, 243 = 3^5, 244 = 2^2*61, 245 = 5^2*49.
5) Поскольку 8 тремя способами раскладывается в произведение множителей: 8, 4*2 и 2*2*2, то по 8 делителей имеют числа вида p^7, p^3*q и p*q*r (p, q, r - простые). Покажем, что больше 7 подряд идущих таких чисел быть не может. Действительно, из 8 подряд идущих чисел одно делится на 2^2, но не делится на 2^3, но такое число не может иметь 8 делителей.
Найти семерку подряд идущих таких чисел (и даже четверку) я оказался неспособен. Однако тоже не вижу причин, почему бы такой семерке не быть.
Эстетическая оценка: как всегда, с нерешенной задачей проблемы. Первые три пункта слишком просты и поэтому неинтересны. А у оставшихся двух я не знаю решения, думаю, что нужен компьютерный перебор. Тем не менее, моя эстетическая оценка - 4 балла. Всегда здорово, что за таким простым по формулировке вопросом оказывается нетривиальная задача. 12.10.07.
За верное решение задачи и ее обобщение Влад Франк получает 11 призовых баллов. За правильное решение задачи Константин Кноп и Анатолий Казмерчук получают по 8 призовых баллов. За верные, но неполные (в разной степени) решения: Олег Полубасов получает 7 призовых баллов; Виктор Филимоненков - 6 баллов; Галина Крюкова - 5 баллов.
Конкурсная задача №79 (А-5) (6 баллов)
Сколько решений имеет нижеприведенная система уравнений?
[x] + {y} = [y]*{x}; x + y = n
Примечания: [x] = floor(x) - целая часть (пол) x; {x} = frac(x) - дробная часть x; n - целочисленый параметр.
Ответ: Бесконечно много решений при n = -1; [n/2] + 1 решение при n >= 0; [|n/2|] решений при n <= -2.
Решение. Случай 1. Если {x} = 0. Тогда из второго уравнения следует, что и {y} = 0, тогда из первого следует, что [x] = 0, то есть x = 0, откуда y = n. То есть при любом n есть одно целочисленное решение.
Случай 2. Пусть x (а значит и y) не являются целыми. Тогда {y} = 1 - {x}, а из второго уравнения следует, что [y] = n - [x] - 1. Подставляя эти выражения в первое уравнения, получим: [x] + 1 - {x} = (n - [x] - 1)*{x}, то есть
n = ([x] + 1)/{x} + [x] (*)
или {x} = ([x] + 1)/(n - [x]) (**)
Каждое решение x этих уравнений дает решение (x,y) исходной системы, поэтому будем решать (*).
При n = -1 равенство (*) выполняется для любого x, при котором [x] = -1. Таким образом, решений в этом случае бесконечно много (континуум).
При n >= 0 равенство (*) выполняется только при [x] >= 0. Поскольку, однако, 0 < {x} < 1, то из (*) следует, что n > 2[x]+1, то есть 0 <= [x] < (n-1)/2. Значит, [x] может принимать [n/2] значений. {x} при каждом таком значении выражается из (**), то есть существует [n/2] + 1 решение системы (с учетом решения из случая 1)
При n <= -2 равенство (*) может выполняться только при [x] <=-2. Поскольку {x} все так же меньше 1, то из (*) следует, что n < 2[x]+1, то есть (n-1)/2 < [x] <= -2. Это дает [|n/2|] - 1 возможное значение [x], по каждому из которых {x} восстанавливается из (**). Значит, с учетом решения из случая 1, имеется [|n/2|] решений системы.
Эстетическая оценка задачи: 3 балла. 24.10.07.
За правильное решение этой задачи Виктор Филимоненков и Анатолий Казмерчук получают по 6 призовых баллов. За верные по сути, но не лишенные неточностей решения: Владислав Франк получает 5 призовых баллов, Константин кноп, Галина Крюкова и Олег Полубасов - по 4 призовых балла, Ефим Подвойский - 3 призовых балла.
Итоги мини-конкурса арифметических задач
1. Владислав Фpанк 32
2. Анатолий Казмерчук 31
3. Виктоp Филимоненков 30
3. Олег Полубасов 30
3. Константин Кноп 30
6. Дмитpий Милосеpдов 10
7. Андpей Богданов 10
8. Сергей Беляев 9
8. Галина Крюкова 9
10. Евгений Машеpов 4
10. Иван Козначеев 4
10. Алекс Кочаpин 4
10. Дмитрий Бобровский 4
10. Сеpгей Аpакчеев 4
15. Ефим Подвойский 3
16. Стас Гpицюк 1