Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Categories:

Математический марафон. 6 тур. Задачи 51-55.

Соберу в кучку свои решения задач математического марафона, проводимого Владимиром Лецко в конференциях RU.MATH и RU.GOLOVOLOMKA. Сюда же буду добавлять решения и остальных задач 6 тура по мере раскрытия ответов на них в конференциях.
Здесь остаются решения задач 51-55, остальные переносятся сюда.


Конкурсная задача №1(51) (3 балла)

1) Какое наибольшее число можно получить, расставляя скобки в выражении
1:2:3:...:n? (1 балл)
2) Верно ли, что для любого положительного рационального числа a существуют такое n и такой способ расстановки скобок, что значение выражения 1:2:3:...:n станет равным а? (2 балла)

Ответы:
1) 1 при n=1; n!/4 при других натуральных n.
2) Нет, не верно.

Решение: 1) При любой расстановке скобок полученное выражение преобразуется к обыкновенной дроби, и каждое из чисел 1,..n является множителем либо в числителе, либо в знаменателе этой дроби. При любой расстановке скобок число 1 оказывается в числителе, а при n>1 число 2 оказывается в знаменателе. Остальные числа 3..n с помощью расстановки скобок 1:((..(2:3):4)..:n) все можно отправить в числитель, что и даст наибольший возможный результат (1*3*4*..*n)/2=n!/4.
2) Например, число a=2 не может быть получено никакой расстановкой скобок, ни при каких n. Действительно, при n=1 и 2 это проверяется непосредственно. Если n>2, обозначим через p наибольшее простое число, не превосходящее n (p>=3). По так называемой аксиоме Бертрана (утверждению, доказанному еще Чебышевым) между числами p и 2p обязательно найдется какое-нибудь простое число. При нашем выборе p это означает, что n<2p, то есть среди чисел 1..n число p единственное, делящееся на p. Таким образом, при любом n и при любой расстановке скобок получится дробь, содержащая либо в числителе, либо в знаменателе некий несократимый множитель p. Но число a=2 не представляется такой дробью.

Моя эстетическая оценка задачи: 2 балла (к сожалению, исправленный наскоро п.1 совсем не получился задачей).
30.07.06.
За правильное решение этой задачки Иван Козначеев, Алексей Ковальский, Виктор Филимоненков и Влад Франк получают по три призовых балла. Дмитрий Милосердов получает 4 призовых балла (один балл добавлен за наиболее оперативную реакцию на мой прокол).

Конкурсная задача №2(52) (11 баллов)
Конечно ли множество натуральных m таких, что количество обратимых элементов в кольце классов вычетов по модулю m равно количеству квадратов в том же кольце?
Ответ: Такое множество конечно. Оно состоит из шести чисел (не считая m=1, при котором классы вычетов не составляют кольцо): 3, 4, 12, 70, 90, 210.

Решение:
1. Обозначим через f(m) количество обратимых элементов в кольце классов вычетов по модулю m, через l(m) количество квадратов в том же кольце, а также z(m)=f(m)/l(m). В задаче нужно найти такие m, для которых z(m)=1.

2. Лемма. Функция z(m) является мультипликативной, то есть если любые натуральные числа a и b взаимно просты, то z(a*b)=z(a)*z(b).

Доказательство. Достаточно доказать, что мультипликативными являются функции f(m) и l(m).
Обратимыми элементами по модулю m являются те и только те остатки от деления на m, которые взаимно просты с m. Действительно, остаток d взаимно прост с m тогда и только тогда, когда существуют такие целые u и v, что ud+vm=1. Но это равносильно тому, что ud=1 по модулю m, то есть класс вычетов, содержащий u, является обратным к классу элемента d.
Таким образом, f(m) это функция Эйлера, мультипликативность которой доказывается во всех учебниках по теории чисел. В частности, я пользуюсь учебником: Бухштаб А.А. Теория чисел. М., Просвещение, 1966.
Мультипликативность функции l(m) тоже утверждение достаточно простое, и доказано во многих учебниках. Для краткости, я сошлюсь на доказательство в книге Цфасмана и Острика из серии «Математическое просвещение»: Алгебраическая геометрия и теория чисел, М., 2005. (стр. 41-42).

3. Лемма. Если p>2 простое число, то z(p)=2(p-1)/(p+1). В частности, z(p) увеличивается с ростом p.

Доказательство: Если p – нечетное простое число, то f(p)=p-1 (очевидно), а l(p)=(p-1)/2+1. Действительно, a^2=b^2(mod p) тогда и только тогда, когда (a-b)(a+b)=0(mod p), а так как p простое, то это возможно либо при a=b(mod p), либо при a=-b(mod p). Таким образом, различными квадратами по модулю p являются 0^2, 1^2 .. ((p-1)/2)^2, а квадраты остальных элементов совпадают с квадратами противоположных элементов.

4. Лемма. z(p^(k))>=z(p^(k-1)) при любом натуральном k>=2 и любом простом p.

Доказательство: f(p^k)=(p-1)p^(k-1) (т.к. взаимно простыми с p^k являются те остатки от деления на p^k, которые не делятся на p, которые не делятся на p). Отсюда f(p^k)=p*f(p^(k-1)).
С другой стороны, l(p^k)<=p*l(p^(k-1)). Действительно, каждый остаток от деления на p^k можно однозначно представить в виде x+c* p^k где 0<=x< p^(k-1), 0<=c<=p-1. Но
(x+c* p^(k-1))^2=x^2+2c*x* p^(k-1)+c^2* p^(2k-2)= x^2+2c*x* p^(k-1) (mod p^k)
(поскольку 2k-2>=k при k>=2). Таким образом, каждый квадрат элемента по модулю p^(k-1) отличается от квадрата некоторого элемента по модулю p^(k-1) на величину, кратную p^(k-1). Значит, каждому квадрату по модулю p^(k-1) соответствует не более p квадратов по модулю p^k, что завершает доказательство леммы.

5. Лемма. z(p^k)<2 при любом натуральном k и любом простом p.

Доказательство: Непосредственно проверяется, что z(2)=0,5. В остальных случаях f(p^k)=(p-1)p^(k-1) – четно. При этом ровно половина остатков от деления на p^k и взаимно простых с p^k меньше, чем p^k/2 (если d меньшее, чем p^k/2, взаимно просто с p^k, то p^k-d больше p^k/2, и p^k-d взаимно просто с p^k). Но если d1 и d2 – два разных взаимно простых с p^k, меньших p^k/2, то их квадраты по модулю p^k различны, иначе (d1-d2)(d1+d2)=0(mod p^k). Но d1-d2 и d1+d2 имеют разные остатки от деления на p, и либо d1-d2=0(mod p^k), либо d1+d2=0(mod p^k). Но и то и другое противоречит выбору d1 и d2. Таким образом, есть f(p^k)/2 различных квадратов по модулю p^k, взаимно простых с p^k, плюс, по крайней мере, еще 0^2=0. Таким образом, l(p^k)>=f(p^k)/2+1, откуда z(p^k)<2.

6. Перейдем к решению уравнения z(m)=1. Пусть m раскладывается на простые множители m=(p1^k1)*..*(ps^ks). По лемме 2 тогда z(m)=z(p1^k1)*..*z(ps^ks). Для решения уравнения тогда нужно подобрать такие множители вида z(p^k), произведение которых равно 1. Но непосредственное вычисление дает:
z(2)=1/2; z(3)=1; z(2^2)=1; z(5)=4/3; z(7)=3/2; z(3^2)=3/2.
Кроме того, z(2^3)=4/3>1, z(5^2)=20/11>1,5. А поскольку по леммам 3 и 4 z(p) растет с ростом p и z(p^k) растет с ростом k, то и для всех остальных p^k верно z(p^k)>1,5 при нечетном p и z(2^k)>1.
Рассмотрим 2 случая. Случай 1. В разложение m входит 2 в первой степени. Тогда в разложение z(m) входит z(2)=1/2, а произведение остальных множителей должно быть равно 2. Поскольку по лемме 5 каждый такой множитель меньше 2, этих множителей должно быть не меньше двух. С другой стороны, два множителя вида z(p^k), каждый из которых больше 1,5 в произведении дадут число больше 2. Таким образом, остается конечное число вариантов, из которых перебором находятся решения:
z(2*3*5*7)=z(210)=z(2)*z(3)*z(5)*z(7)=1/2*1*4/3*3/2=1
z(2*5*7)=z(70)=z(2)*z(5)*z(7)=1/2*4/3*3/2=1
z(2*3^2*5)=z(90)=z(2)*z(3^2)*z(5)=1/2*3/2*4/3=1.
Случай 2. В разложение m 2 входит не в первой степени. Но тогда все множители вида z(p^k) в разложении z(m) не меньше 1, и равенство z(m)=1 возможно только если все z(p^k) в разложении равны 1. Это дает еще три решения:
z(3)=1
z(2^2)=z(4)=1
z(3*2^2)=z(12)=1.
Конец решения задачи.

Моя эстетическая оценка задачи: 4 балла.
30.07.06 г.

За правильное решение этой задачи Виктор Филимоненков и Влад Франк получают по 11 призовых баллов.

Конкурсная задача №3(53) (8 баллов)

Hайти самое маленькое число, допускающее представление в виде суммы шести
слагаемых, обладающее следующими свойствами:
1) каждое слагаемое является натуральным числом;
2) любые два слагаемых не взаимно просты;
3) любые три слагаемых взаимно просты;
4) сумма любых четырех слагаемых кратна 4;
5) сумма любых пяти слагаемых кратна 5.

Мой ответ: 37.895.842 – наименьшее из чисел, найденных мною.
Оно является суммой шести чисел:
7179887 = 11*13*23*37*59
7070147 = 7*17*19*53*59
11299067 = 13*17*29*41*43
2874567 = 3*19*29*37*47
4648047 = 3*23*31*41*53
4824127 = 7*11*31*43*47
Эти числа удовлетворяют условиям:
1) - очевидно,
2) - так как любые два имеют в разложении общий простой множитель,
3) - так как каждый простой множитель входит в разложение только двух из шести чисел,
4) и 5) - так как все числа имеют одинаковый остаток 7 от деления на 20, то есть одинаковые остатки 3 от деления на 4 и одинаковые остатки 2 от деления на 5.

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

Эстетической оценки задачи дать не могу, так как не знаю решения. Могу оценить в 4 балла эстетическое удовольствие, полученное мною при решении задачи.
18.08.06.

Комментарии. Минимальным решение оказалось 34882142, сумма чисел:
6109697 = 11*19*23*31*41,
5675097 = 3*29*37*41*43,
4849977 = 3*11*47*53*59,
7156877 = 7*13*31*43*59,
5367257 = 7*17*23*37*53,
5723237 = 13*17*19*29*47
К сожалению, и само решение, и доказательство его минимальности основано на компьютерном переборе, что, по-моему, снижает эстетическую оценку. Я-то относился к поиску возможно меньшего решения со спортивнмым интересом. Хотя, если бы у меня было минимальное решение, наверное, можно было подумать о сведении доказательства минимальности хотя бы до уровня ручного перебора. Я программу писать не стал, не потому, что не умею пользоваться отверткой (тоже мне, бином Ньютона), а просто не знаю, где у меня эта отвертка лежит.

За решение этой задачи Влад Франк получает 8 призовых баллов. Виктор Филимоненков, которому (при правильных рассуждениях) не удалось найти минимальное число, получает 4 призовых балла. Hаиболее полное исследование прислал Олег Полубасов. Олег заявил, что выступает вне конкурса. Поэтому мне ничего не остается, кроме как оценить его решение в 10 внеконкурсных призовых баллов ;)

Конкурсная задача №4(54) (3 баллa)
Доказать, что максимум площадей четырехугольников со сторонами a, b, c, d не
зависит от порядка следования сторон.

Решение:
1. Максимум площадей четырехугольников с данными сторонами и порядком их следования достигается на выпуклом четырехугольнике. Действительно, если в четырехугольнике есть угол, больше развернутого, отобразим две стороны, составляющие этот угол, относительно прямой, проходящей через не общие концы этих сторон. Получится четырехугольник с тем же порядком следования сторон, содержащий исходный невыпуклый четырехугольник, то есть больший по площади.
2. Обозначим M(a,b,c,d) наибольшую площадь четырехугольников со сторонами a,b,c,d и указанным циклическим порядком сторон (скажем, по часовой стрелке).
Докажем, что от перестановки порядка следования любых двух соседних сторон эта наибольшая площадь не меняется. Например, докажем, что M(a,b,c,d)=M(a,b,d,c).
Действительно, возьмем четырехугольник со сторонами a,b,c,d и указанным порядком сторон, на котором достигается максимум M(a,b,c,d). Отразим стороны c и d относительно серединного перпендикуляра к отрезку, соединяющего не общие концы сторон c и d. Поскольку по п.1 выбранный четырехугольник выпуклый, то полученная фигура тоже будет четырехугольником, причем той же площади M(a,b,c,d), но уже с порядком следования сторон a, b, d, c. Таким образом, M(a,b,c,d)<=M(a,b,d,c). Но аналогично M(a,b,c,d)>=M(a,b,d,c).
3. Осталось заметить, что с помощью таких транспозиций соседних сторон мы можем получить любой порядок следования сторон. Вот, например, как с помощью последовательного применения таких транспозиций получаются все возможные циклические перестановки сторон из исходной перестановки (a,b,c,d):
(a,b,c,d)-(a,b,d,c)-(a,d,b,c)-(a,d,c,b)-(a,c,d,b)-(a,c,b,d).

Моя эстетическая оценка задачи: 3 балла.
30.07.06.

Комментарий. Это мое решение приведено Владимиром Лецко как пример решения, доступного для понимания семиклассникам. Рассматриваю это как замечательный комплимент своему умению объяснять. Это умение отточено, безусловно, на студентах, которые часто не дотягивают до уровня седьмого класса, а объяснить им надо.
За правильное решение этой задачи Виктор Филимоненков, Влад Фpанк и Иван Козначеев получают по 3 призовых балла.

Конкурсная задача №5(55).
а) Через точку внутри тетраэдра провели 4 плоскости, параллельные граням. Hа сколько частей разобьется тетраэдр? (1 балл)
б) Какой наименьший объем может иметь тетраэдр, если объемы частей попарно различны и целочисленны? (6 баллов).

Решение:
а) Ответ. На 14 частей.
Доказательство. Обозначим через S(n) количество частей, на которые разбивают выпуклую пространственную фигуру n несовпадающих плоскостей, проходящие через одну точку внутри этой фигуры. Проведем (n+1)-ую плоскость. Она пересечет n плоскостей, и будет разбита прямыми пересечения на 2n углов. Каждый из этих углов (точнее, тот кусок угла, который лежит внутри фигуры) делит на две части одну из S(n) частей разбиения. Таким образом, S(n+1)=S(n)+2n. Поскольку S(1)=2 (очевидно), то S(2)=4, S(3)=8, S(4)=14. Вообще: S(n)=2+2+4+6+8+...+2(n-1)=2+n(n-1), n>=1.

б) Ответ. 14^3=2744.
Доказательство.
1. Пусть M – точка, через которую проведены плоскости; k – объем тетраэдра; a, b, c, d – объемы тетраэдров T1, T2, T3, T4, на которые разбивается исходный тетраэдр треугольниками, образованными ребрами этого тетраэдра и отрезками, проведенными от M к вершинам тетраэдра. Тогда a+b+c+d=k.

2. Всегда можно выбрать точку M внутри тетраэдра так, чтобы числа a, b, c, d были заданной четверкой положительных чисел, удовлетворяющих равенству a+b+c+d=k.
Действительно, объемы тетраэдров T1, T2, T3, T4 при данных площадях граней исходного тетраэдра определяются их высотами, то есть расстояниями от точки M до граней. Возьмем в качестве точки M точку пересечения трех плоскостей, проведенных параллельно граням исходного тетраэдра на таком расстоянии, чтобы объемы T1, T2, T3 были равны a, b и c. Эта точка будет лежать внутри тетраэдра, поскольку иначе a+b+c>=k (объединение T1, T2, T3 будет целиком содержать исходный тетраэдр), что противоречит заданию чисел a, b, c, d. Тогда и объем тетраэдра T4 будет равен d.

3. Через a, b, c, d легко могут быть вычислены объемы 14 частей, на которые разбивают тетраэдр плоскости. Среди этих частей:
4 параллелепипеда с гранями, параллельными трем граням исходного тетраэдра, (по одному параллелепипеду у каждой вершины тетраэдра). Объемы этих параллелепипедов:
6abc/(k^2), 6abd/(k^2), 6acd/(k^2), 6bcd/(k^2);
4 тетраэдра, подобных исходному, (по одному тетраэдру, стоящему на каждой грани исходного тетраэдра). Объемы этих частей:
a^3/(k^2), b^3/(k^2), c^3/(k^2), d^3/(k^2);
6 шестигранных фигур, (по одной фигуре, примыкающей к каждому ребру тетраэдра). Объемы этих частей:
3ab(a+b)/(k^2), 3ac(a+c)/(k^2), 3ad(a+d)/(k^2), 3bc(b+c)/(k^2), 3bd(b+d)/(k^2), 3cd(c+d)/(k^2).

4. Если все 14 чисел, указанных в пункте 3, являются целыми, то и a, b, c, d являются целыми.
Действительно, поскольку, например, 6abc/(k^2) и 3ab(a+b)/(k^2) – целые, то (a+b)/c – рационально. Аналогично (a+d)/c и (b+d)/c рациональны, а, значит, (a+b+d+c)/c рационально. Но, поскольку a+b+c+d=k – целое, то и с рационально. Аналогично, a, b, d рациональны.
Далее, поскольку a^3/(k^2) целое, то a^3 целое, а поскольку число a рационально, то оно тоже целое. Аналогично b, c, d целые.

5. Если k – минимальное целое число, удовлетворяющее условиям задачи, то k является кубом целого числа.
Пусть, напротив, какой-то из простых множителей x входит в разложение k в степени 3m+p, где p = 1 или 2. Тогда, поскольку a^3/(k^2) целое, число a (и, аналогично, b, c, d) делятся на x^(2m+p). Но тогда все числа k, a, b, c, d можно одновременно сократить на x, при этом все 14 чисел, указанных в пункте 3 останутся целыми. Но это будет противоречить минимальности k.

6. Таким образом, k = n^3 для некоторого целого n. При этом каждое из чисел a, b, c, d делится на n^2, в силу целости чисел a^3/(k^2), b^3/(k^2), c^3/(k^2), d^3/(k^2). Пусть a = a1*n^2, b = b1*n^2, c = c1*n^2, d = d1*n^2. Тогда, в силу a+b+c+d = k получим a1+b1+c1+d1 = n. Поскольку a, b, c, d, (иначе одинаковы объемы частей разбиения), значит, и a1, b1, c1, d1 различные, и тогда n>=10. Рассматривая все наименьшие возможные разложения натуральных чисел в сумму четырех различных слагаемых (10=1+2+3+4, 11=1+2+3+5, 12=1+2+3+6=1+2+4+5, 13=1+2+3+7=1+2+4+6=1+3+4+5) и придавая значения слагаемых числам a1, b1, c1, d1, убеждаемся, что в каждом случае некоторые из 14 чисел, перечисленных в п. 3, оказываются равными. В то же время для разложения 14=1+3+4+6 получаем 14 различных объемов частей разбиения:
72, 108, 144, 432, 1, 27, 64, 216, 36, 60, 126, 252, 486, 720.
В силу п. 2 разбиение любого тетраэдра объема 14^3 на такие части существует.

Моя эстетическая оценка задачи: 3 балла.
14.10.06 г.
За правильное решение этой задачи Виктор Филимоненков получает 7 призовых баллов, а Влад Франк и Иван Козначеев (они не обошлись без компьютерного перебора) - по 6 призовых баллов.
Под натиском убедительных аpгументов маpафонской общественности я таки пеpесмотpел пpизовые баллы за pешение задачи №55. Влад Фpанк и Иван Козначеев получают по 7 пpизовых баллов. Hо, поскольку pешение Виктоpа Филимоненкова по-пpежнему пpедставляется мне более изящным, он получает дополнительный пpизовой балл.
Таким обpазом, окончательные баллы за pешение задачи №55: Виктоp Филимоненков - 8 баллов; Влад Фpанк - 7 баллов; Иван Козначеев - 7 баллов.


Tags: Задачи, Математика
Subscribe

  • Словесные игры 40

    Предыдущие словесные игры: 1-5, 6-10, 11-15, 16-20, 21-25, 26-30, 31-35, 36-40, 41-45, 46-50, 51-55, 56-60, 61-65, 66-70,…

  • Коробка с красным померанцем

    Мне уже случалось фотографировать это слово из трех букв - меня позабавило тогда, что оно похоже на ручки на газовой плите, у которой две конфорки…

  • Словесные игры 39. Вопрос 195

    Также в игре: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), Вопрос 194 (две строчки), Сегодня последняя загадка 39…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments