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

Category:

ММ-7. Задачи, не входящие в тематический конкурс.

В этот пост я буду складывать задания 7 тура математического марафона, проводимого Владимиром Лецко на http://www.fizmat.vspu.ru:8000/doku.php?id=marafon:about, не входящие в тематический конкурс "Логика". Здесь же я буду публиковать свои решения этих задач после того, как решения будут опубликованы по указанной выше ссылке.
Будет неплохо, если этот пост послужит эффективной рекламой марафона для моих читателей.
Аналогичный пост с заданиями тематического конкурса "Логика".


Конкурсная задача №62 (6 баллов)
Тетраэдр, имеющий площадь поверхности S, сумму длин ребер L, сумму двугранных углов U и сумму трехгранных углов W, рассекли плоскостью на два тетраэдра.
1) Какие значения может принимать S_1 + S_2 - сумма площадей поверхностей
образовавшихся тетраэдров?
2) Какие значения может принимать L_1 + L_2?
3) Какие значения может принимать U_1 + U_2?
4) Какие значения может принимать W_1 + W_2?
Примечания: Под тетраэдром понимается произвольная треугольная пирамида. Каждый пункт представляет собой самостоятельную задачу. То есть выражать, например, возможные значения U_1 + U_2 надо только через U, без учета других характеристик исходного тетраэдра. Трехгранные углы тетраэдра измеряются в стерадианах. (Полный телесный угол равен 4*Pi стерадиан).

Ответы. Во всех случаях это открытые интервалы:
1) (S; 2S); 2) (L; 7/3*L); 3) (U+2*Pi; U+3*Pi); 4) (W; W+2*Pi)
Решение. Если плоскость рассекает тетраэдр на два тетраэдра, то она проходит через одно из ребер. Действительно, такая плоскость должна пересекать хотя бы одно ребро. Тогда обе грани, которые пересекаются по этому ребру, плоскость должна рассекать на 2 треугольника, а, значит, должна проходить через противоположную вершину. Вместе с этими двумя вершинами плоскость проходит и через ребро, их соединяющее.
Обозначения: Пусть исходный тетраэдр ABCD, секущая плоскость проходит через ребро AB и пересекает CD в точке E.
Заметим, что при непрерывном перемещении вершин тетраэдра и точки E параметры, значения которых надо оценить, тоже изменяются непрерывно. Поэтому достаточно указать положение точек ABCDE, при которых оцениваемые параметры сколь угодно близки к границам интервалов, указанных в ответе и доказать, что параметры не могут принимать значений вне этих интервалов.

1) Сумма площадей полученных тетраэдров состоит из площади исходного тетраэдра и двух площадей треугольника АВЕ (будем обозначать эту площадь просто АВЕ). Но АВЕ < АВС+ВСЕ+АСЕ и АВЕ < ABD+ADE+ABE (наверное, это называется неравенством тетраэдра). Значит, 2*АВЕ < АВС+ВСЕ+АСЕ+ABD+ADE+ABE = S.
Если ребро AD много меньше остальных ребер тетраэдра, то при движении точки E по ребру CD от D к С площадь АВЕ меняется от 0 до S/2, а, значит, S_1 + S_2 изменяется от минимального значения S до максимального 2S (исключая границы).
2) Сумма длин ребер полученных тетраэдров состоит из суммы длин ребер исходного тетраэдра, удвоенных длин ребер АЕ и ВЕ и ребра АВ. Но 2*АЕ < AC+AD+CD и 2*BE <
ВС+BD+СD (из неравенства треугольников). Значит, 2*AE+2*BE+AB < AC+AD+CD+ ВС+BD+СD + AB = L +CD. Но СD<1/3*L (т. к. CD < AC+AD и СD < BC+BD). Значит, L_1 + L_2 превышает L на величину, не большую чем 4/3*L.
Если точка С расположена от вершин А, B, D на расстояние много большее, чем расстояние между самими этими вершинами, то при движении точке Е от D к С L_1 + L_2 меняется от минимального L до максимального 7/3*L (исключая границы интервала).
3) Сумма двугранных углов полученных тетраэдров состоит из суммы двугранных углов исходного тетраэдра, углов при ребре АЕ в каждом из двух новых тетраэдров (в сумме дающих pi радиан), углов при ребре ВЕ в каждом из двух новых тетраэдров (в сумме дающих pi радиан), и еще одного угла при ребре CD. Этот угол, очевидно, может меняться от 0 до pi (исключая границы)
4) Честно говоря, впервые задумался о том, знаю ли я, как измеряются трехгранные углы. Выходит, что не знаю. Полагаю, однако, что мера трехгранных углов обладает свойством аддитивности, а большего для решения не нужно.
Сумма трехгранных углов при вершинах полученных тетраэдров равна сумме трехгранных углов исходного тетраэдра и двух углов при вершине Е, дающих в сумме четырехгранный телесный угол с двумя сторонами (EC и DC), образующими развернутый угол. Этот угол может меняться от 0 до половины полного телесного угла, то есть 2*pi стерадиан.

Эстетическая оценка задачи: 3 балла. 27.02.07.
Задача оказалась значительно труднее первой задачи. В присланных решениях немало ошибок (затруднения вызвали пункты с четными номерами). Я не снижал оценок за те решения, авторы которых прошли мимо нюансов, рассмотренных в Обсуждении (я ведь и сам прошел мимо них, когда оценивал задачу). Вместо этого я добавил поощрительный балл Владиславу Франку, обратившему мое внимание на тонкости "угловых" пунктов.
Ряд марафонцев прислали чрезмерно краткие решения (а то и вовсе только ответы).
Разумеется, это отразилось на их оценках. В итоге призовые баллы распределились так:
Олег Полубасов, Виктор Филимоненков и Андpей Богданов - по 6 призовых баллов; Иван Держанский - 5 призовых баллов; Владисдав Франк и Сергей Аракчеев - по 4 призовых балла; Алексей Кутузов - 3 призовых балла.


Конкурсная задача №64 (6 баллов)
Доказать, что уравнение 2x^2 + 4y^4 + 7z^7 = t^13 имеет:
1) бесконечно много решений во множестве четных натуральных чисел;
2) бесконечно много решений во множестве нечетных натуральных чисел;
3) бесконечно много решений, в каждом из которых есть как четные, так и нечетные числа, во множестве целых чисел.

Решение: Заметим, что если (x, y, z, t) какое-то решение уравнения во множестве, указанном в 1), 2) или 3), то при любом нечетном натуральном p четверка (x*p^182; y*p^91; z*p^52; t*p^28) также является решением в том же множестве. Таким образом, в каждом из трех множеств достаточно найти по одному решению. Такими решениями являются, например:
для 1): (2^17; 2^9; 2^5; 2^3);
для 2): (3^122; 3^61; 3^35; 3^19);
для 3): (2; 0; -1; 1).

Эстетическая оценка задачи: 3 балла. 19.02.07.
За решение задачи № 64 Сергей Аракчеев, Олег Полубасов, Виктор Филимоненков и Владислав Франк получают по 6 призовых баллов. Алексей Кутузов, справившийся с первыми двумя пунктами, получает 4 призовых балла, Андрей Богданов, решивший только первый пункт, получает 2 призовых балла.

Конкурсная задача №66 (8 баллов)
Двое играют в такую игру:
Каждый игрок очередным своим ходом берет из кучки, содержащей n камней, некоторое количество камней. За один ход можно взять количество камней, являющееся целой неотрицательной степенью одного из двух фиксированных натуральных чисел a и b.
Выигрывает тот, кто возьмет последний камень.
1. Существуют ли такие a и b, при которых шансы на выигрыш у второго игрока выше, чем у первого?
2. Оценить шансы игроков для случаев, когда a и b - простые числа.
3. Перед началом игры игроки делают ставки. Обе ставки забирает победитель. Ставка первого игрока в пять раз больше. Зато первый игрок имеет право (до того как узнает число n) выбрать числа a и b. Кому из игроков выгодны такие условия?
Примечания: 1. Число "камней" n для каждой игры выбирается случайно из диапазона [1.. 1000000] (распределение равномерное). 2. Соперники играют наилучшим образом.

1. Ответ: нет.
Решение. Благоприятными для второго игрока значениями n являются такие, при которых после любого хода первого игрока у второго игрока есть выигрышная стратегия. В частности, если первый берет один камень, у второго есть выигрышная стратегия. Но это значит, что если бы камней было n-1, у первого игрока была бы выигрышная стратегия. Учитывая, что n = 1 благоприятно для первого игрока, получаем, что благоприятных для первого игрока чисел по крайней мере не меньше.
2. Ответ. а) Если числа a и b нечетны, то шансы равны.
б) Если одно из чисел равно 2, а второе не делится на 3, то шансы первого игрока 666667:333333.
в) Если числа 2 и 3, то шансы первого игрока 4:1
Решение. а) Если a и b нечетны (причем не обязательно простые), то нечетны и любые их степени, а значит четность числа камней в куче меняется после каждого хода. Значит, первый игрок выиграет, если изначально количество камней в куче нечетно, а второй – если четно. Поскольку четных и нечетных чисел среди миллиона поровну, то шансы игроков равны.
б) Если n не делится на три, то первый игрок имеет выигрышную стратегию: каждым своим ходом (1 или 2 камня) он делает число камней в куче кратным 3, после чего второй, как бы не сходил, снова оставит в куче не кратное 3 число камней. Соответственно, если n кратно трем, то выигрывает второй.
в) Если n не кратно 5, то первый игрок имеет выигрышную стратегию: каждым своим ходом (1, 2, 3 или 4 камня) он делает число камней в куче кратным 5, после чего второй, как бы не сходил, снова оставит в куче не кратное 5 число камней. Соответственно, если n кратно 5, то выигрывает второй.
3. Ответ. Такие условия выгодны первому игроку.
Решение. Вопрос можно переформулировать так: можно ли выбрать такие a и b, при которых доля благоприятных для второго игрока значений n меньше 1/6.
При произвольных a и b распределение благоприятных для второго игрока значений n довольно сложное, поэтому пришлось воспользоваться компьютерным перебором. Опишу составленный мною алгоритм, который при фиксированных a и b находит множество благоприятных для второго игрока значений n. Алгоритм сродни решету Эрастофена.
1. Вычеркиваем из натурального ряда числа 1, a, a^2, … , b, b^2, … - эти значения n благоприятны для первого игрока.
2. Двигаясь по натуральному ряду, ищем очередное не зачеркнутое число x– оно благоприятно для второго.
3. Вычеркиваем из натурального ряда все числа вида x+1, x+a, x+a^2, … , x+b, x+b^2 … - они благоприятны для первого.
4. Возвращаемся к 2.
Продолжаем, пока не кончится натуральный ряд :) Реально, конечно, ограничимся конечным отрезком натурального ряда. В задаче этот отрезок из 1000000 чисел.
Поскольку сам я языки программирования знаю только со словарем, программу мне помогал писать и тестировать девятиклассник из нашего города Дима Труфанов. Мы получили, что при a=2, b=33 выигрышными для второго игрока являются только 7779 чисел из первых 60000, то есть меньше даже, чем 1/7.
К сожалению, в силу того, что объем массива из 0 и 1 в используемом нами языке возможен максимум 2^16, мы не смогли проверить, какова доля благоприятных для второго игрока чисел среди первого миллиона чисел. Так что, строго говоря, решения п. 3 у меня нет, а есть только убежденность (плохо обосновываемая), что при a=2 и b=33 шансы второго игрока по крайней мере, остаются на уровне не выше 1/7. Но у меня нет средства это проверить (по крайней мере, по указанным алгоритму).
Эстетическая оценка: 3 балла, если п. 3 не имеет некомпьютерного решения, 4 балла – если есть некомпьютерное решение. 8.04.07.
За правильное решение этой задачи Олег Полубасов получает 8 призовых баллов. За правильное (но не совсем строгое) решение Виктор Филимоненков получает 7 призовых баллов. За верное решение пунктов 1 и 2 Андрей Богданов и Владислав Франк получают по 4 призовых балла.

Конкурсная задача №68 (5 баллов)
1. Доказать, что для любого натурального n найдется натуральное k такое, что числа Фибоначчи F(k), F(k+1), ..., F(k+n-1) являются составными.
2. Какое наибольшее количество простых чисел может встретиться среди десяти идущих подряд чисел Фибоначчи?
Примечания: 1. Рекуррентое определение чисел Фибоначчи: F(1) = F(2) = 1, F(n+1) = F(n) + F(n-1) при n > 2. 2. Напомню, что 1 не является ни простым, ни составным числом.

Решение.
Лемма. Для любых натуральных m и l число Фибоначчи F(l*m) делится на число Фибоначчи F(m).
Доказательство леммы. Положим дополнительно F(0) = 0 (тогда рекуррентная формула для чисел Фибоначчи верна уже начиная с n>1). Рассмотрим числа Фибоначчи F(m-i) и F(m+i) по модулю F(m). Из рекуррентной формулы, остающейся верной по любому модулю, легко увидеть, что F(m-i) = F(m+i) (mod F(m)), если i нечетно, и F(m-i) = -F(m+i) (mod F(m)), если i четно. Таким образом, если одно из чисел F(m-i) и F(m+i) по модулю F(m) оказывается равным 0, то и второе тоже равно нулю. Но поскольку F(m-m) = F(0) = 0 по любому модулю, то и F(2*m) равно 0 по модулю F(m), то есть делится на F(m). Рассуждая аналогично о числах F(2*m-i) и F(2m+i), получим, что F(3*m) = F(2*m+m) = F(2*m-m) = F(m) = 0 (mod F(m)), и так далее, то есть F(l*m) = 0 (mod F(m)) для любого l.
Перейдем к решению п.1. Для заданного числа n возьмем, например, k = (n+2)!+3. Тогда при i от 0 до n-1 выполнено: F(k+i) = F((n+2)!+3+i) = F((i+3)*(натуральное)), что в силу леммы делится на F(i+3) > 1, то есть является составным.
В п. 2 ответ: 5. Действительно, таково, например, количество простых чисел среди чисел Фибоначчи F(3), …, F(12). По лемме, число Фибоначчи является простым, только если его номер прост (за исключением простого F(4) = 3). Поскольку среди 10 любых подряд идущих чисел только 4 не делятся на 2 или 5, начиная с n > 5 среди чисел F(n), …, F(n+9) не больше четырех простых. То, что при n = 1, 2, 3, 4, 5 количество простых среди таких чисел не больше 5, проверяется непосредственно.
Эстетическая оценка задачи – 5 баллов. 19.04.07.
За правильное решение этой задачи Сергей Аракчеев, Андрей Бежан, Сергей Беляев, Евгений Машеров, Олег Полубасов, Виктор Филимоненков и Влад Франк получают по 5 призовых баллов.

Конкурсная задача №70 (12 баллов)

В k-круговом шахматном блицтурнире приняли участие n шахматистов. В итоговой таблице никакие два участника не набрали поровну очков (т.е. в терминах задачи 48 турнир оказался правильным).
На торжественном закрытии турнира участник, занявший последнее место, заметил, что, если бы очки начислялись так же как в футболе, он занял бы не последнее, а первое место.
Более того, при подсчете очков по футбольным правилам, никакие два участника по-прежнему не имели бы поровну очков, но при этом выстроились бы в итоговой таблице в обратном порядке.

1. Какое наименьшее число партий могло быть сыграно в таком турнире?
2. При каком наименьшем k возможна описанная ситуация?
3. При каком наименьшем n достигается наименьшее k, при котором возможна такая ситуация?
Примечания:
В k-круговом турнире каждый участник встречается с каждым k раз. За победу в партии в шахматном турнире начисляется одно очко, за ничью пол-очка, а за поражение ноль очков. За победу в матче в в футбольом турнире начисляется три очка, за ничью одно очко, а за поражение ноль очков. Разумеется, в турнире участвует более одного шахматиста.

Ответы. 1. 30 партий. 2. При k = 6. 3. При n = 11.
Решение. Во-первых, заметим, что если умножить на 2 все очки, полученные в турнире, распределение мест от этого не изменится. Поэтому будем, для удобства, считать, что такая деноминация очков проведена, и за победу в турнире дается 2 очка, за ничью одно очко, за поражение 0. Такую систему начисления очков будем называть «старой», а систему, при которой очки начисляются как в футболе «новой»

Лемма. Если участник А набрал по старой системе меньше очков, чем Б, а по новой системе больше, чем Б, то у А по крайней мере на 2 победы и 3 поражения больше, чем у Б, и по крайней мере на 5 ничьих меньше, чем у Б.
Доказательство леммы: Пусть А одержал x побед, сделал y ничьих и потерпел z поражений, а Б соответственно x-r, y+s, z-t. Тогда, сравнивая их очки по старой системе, получим: 2x+y < 2(x-r)+(y+s), или 2r < s. По новой системе: 3x+y > 3(x-r)+(y+s), или 3r > s. Так как s и r целые, такое возможно только при r >= 2, и, соответственно, s >= 5. Поскольку по старой системе Б набрал больше очков, то t > r, то есть t >=3.

1. Ясно, что в турнире с двумя игроками описанная в условии ситуация невозможна. Приведем пример турнира, с n = 3 участниками из k = 10 кругов, в котором могла произойти указанная в условии задачи ситуация. Для каждой пары участников тройка чисел в:н:п обозначает количество выигрышей, ничьих, поражений в играх между ними.
А-Б 0:10:0, А-В 3:5:2, Б-В 5:0:5.
По старой системе А получит 21 очко, Б 20 очков, В 19 очков. По новой системе А получит 24 очка, Б 25 очков, В 26 очков, то есть порядок мест поменялся на обратный.
Покажем, что для трех игроков наименьшее возможное число кругов 10. Действительно, пусть порядок убывания мест по старой системе А, Б, В. Тогда по лемме, В сделал минимум на 5 ничьих меньше, чем Б, а Б на 5 меньше, чем А. То есть А сделал минимум на 10 ничьих больше, чем В, то есть сыграл с Б по крайней мере 10 матчей (вничью, больше не с кем). Так что кругов по крайней мере 10.
Покажем, что при больших n количество игр не меньше 30. Действительно, всего игр n*(n-1)*k/2. Но по п.2 задачи k >= 6, так что при n >= 4 общее число игр не меньше 36.

2. Из леммы следует, что первый по старой системе участник сыграл минимум 5*(n-1) раз вничью (если последний участник не играл вничью вовсе). Плюс к этому он одержал хотя бы 1 победу (иначе не занял бы 1 место). Значит, поскольку в каждом круге участник играет n-1 партию, количество кругов не меньше 6.
Приведем пример турнира из n = 11 игроков с k = 6 кругами, при котором могла возникнуть указанная в условии задачи ситуация. Для каждого участника указано общее соотношение количеств побед:ничьих:поражений == число очков по старой системе == число очков по новой системе.
А 5:55:0 == 65 == 70
Б 7:50:3 == 64 == 71
В 9:45:6 == 63 == 72
Г 11:40:9 == 62 == 73
Д 13:35:12 == 61 == 74
Е 15:30:15 == 60 == 75
Ж 17:25:18 == 59 == 76
З 19:20:21 == 58 == 77
И 21:15:24 == 57 == 78
Й 23:10:27 == 56 == 79
К 25:5:30 == 55 == 80
Результаты матчей между игроками могли быть, например, такими:
А, Б, В, Г, Д и Е друг с другом сыграли 0:6:0. Участники, сумма мест которых по старой системе 13 или больше, сыграли между собой 3:0:3 (кроме матчей Ж-К 5:0:1 и З-Й 4:0:2). Остальные матчи окончились со счетом 1:5:0 в пользу игроков, набравших большее число очков по старой системе.

3. Осталось показать, что меньше 11 участников при k = 6 кругах быть не может. Действительно, пусть l = [n/2]. Из леммы следует, что каждый из первых (по старой системе) l участников сделал по крайней мере на 5*l ничьих больше, чем участник, стоящий на l мест ниже, то есть в сумме у первых l по крайней на 5*l^2 ничьих больше, чем у следующих l. Эти ничьи первые l участников могли сделать между собой и (при n нечетном) с последним участником. Но при k = 6 между собой эти l игроков могли сделать максимум 6*l*(l-1) ничьей (учитывая каждую ничью у обоих сделавших ее игроков).
Значит, при четном n должно выполняться неравенство 5*l^2 <= 6*l*(l-1), что возможно при l >= 6, то есть минимум при 12 игроках.
При нечетном n должно выполняться неравенство:
5*l^2 <= 6*l*(l-1) + число ничьих у последней команды.
Но последний игрок не может сделать больше l = (n-1)/2 ничьих.
Действительно, у него, по лемме, не меньше 3*(n-1) поражений.
Количество побед у него не меньше 2,5*(n-1). В противном случае первый по старой системе игрок, опять же по лемме, имел бы меньше, чем 2,5*(n-1) – 2*(n-1) = (n-1)/2 побед. В этом случае у первого игрока разность побед и поражений была бы меньше (n-1)/2. У каждого следующего игрока эта разность по крайней мере на 1 меньше (поскольку этой разностью определяется количество очков по старой системе). Тогда суммарное количество побед и у всех игроков и суммарное количество поражений у всех игроков различны (что невозможно).
Значит, всего побед и поражений у последнего по старой системе участника не меньше, чем 5,5*(n-1). Но за 6 кругов он сыграл 6*(n-1) партий, то есть на ничьи остается не больше l = (n-1)/2 партий. Неравенство:
5*l^2 <= 6*l*(l-1) + число ничьих у последней команды <= 6*l*(l-1) + l
выполняется при l >= 5, то есть при n >= 5*2+1 = 11 участниках.

Моя эстетическая оценка задачи: 4 балла. 18.05.07.
За правильное решение этой задачи Виктор Филимоненков, Влад Франк, Андрей Богданов и Олег Полубасов получают по 12, а Сергей Беляев -11 призовых баллов.

ИТОГИ СЕДЬМОГО ТУРА МАТЕМАТИЧЕСКОГО МАРАФОНА
1. Олег Полубасов 65
2. Виктор Филимоненков 64
3. Влад Франк 59
4. Андрей Богданов 52
5. Сергей Аракчеев 35
6. Дмитрий Грицюк 27
8. Сергей Беляев 24
8. Алексей Кутузов 24
10. Евгений Машеров 17
11. Иван Держанский 16
11. Константин Кноп 16
13. Олег Чечулин 15
13. Татьяна Шемелова 15
15. Иван Козначеев 8
15. Ольга Павлова 8
17. Алекс Кочарин 7
17. Виталий Мусихин 7
19. Андрей Бежан 5
19. Владимир Романов 5
19. Мария Рыкалина 5
22. Дмитрий Гусев 4
22. Валентина Загороднюк 5
22. Александр Клешнин 4
Tags: Задачи, Математика
Subscribe

  • 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.
  • 2 comments