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

Category:

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

По адресу http://www.fizmat.vspu.ru:8000/doku.php?id=marathon:about проходит восьмой тур "Математического марафона", проводимого Владимиром Лецко.
По традиции, создаю у себя посты, в которых буду выкладывать свои решения задач по мере открытия ответов на них.
Помимо прочего, этот пост служит рекламой марафона. Присоединяйтесь! Решения можно посылать по адресу, указанному по приведенной выше ссылке.
В рамках тура проводится тематический конкурс "Арифметика", состоящий из 5 задач. Задачам тематического конкурса 8 тура посвящен отдельный пост:
http://fiviol.livejournal.com/30741.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

Конкурсная задача №72 (5 баллов)
Если Вы читали первую книгу про Гарри Поттера, то наверняка помните загадку Снейпа. (Примечание ведущего: не читал, не смотрел, не помню.)
В ряд стоят 7 бутылочек.
Из 7 бутылочек одна позволяет пройти вперед, одна - вернуться назад, в двух вино и в трех яд. Известно, что:
1) слева от вина - всегда яд;
2) по краям - различные напитки, но ни один из них не дает идти вперед;
3) ни самая маленькая, ни самая большая бутылочка не содержат яд;
4) вторая и шестая содержат одно и то же;
Гермиона смогла по этим данным и, видя бутылочки, определить, что зелье для прохода вперед находится в самой маленькой бутылочке, а зелье для прохода назад - в самой правой.
1. Что находится в пятой (слева) бутылочке?
2. Что находится в самой большой бутылочке?

Ответы. 1. Яд. 2. Вино.
Решение. Покажем сначала, что самая большая либо самая маленькая бутылочки стоят второй или шестой. Если это не так, то всегда можно так разлить напитки, что требования 1-4 выполняются, а выводы Гермионы нет (а, значит, она не смогла бы сделать эти выводы). Действительно, нальем яд в бутылочки 2 и 6 и вино в бутылочки 3 и 7 (так как бутылочка 7 самая правая, это уже будет противоречить выводам Гермионы). Из трех оставшихся бутылочек по крайней мере одна ни самая большая, ни самая маленькая, нальем ее в яд. Напиток, позволяющий идти вперед, нальем в любую из двух оставшихся бутылок, не стоящую первой. В оставшуюся нальем напиток, позволяющий идти назад. Легко видеть, что все условия 1-4 выполнены, а Гермиона не сможет отвергнуть гипотезу о таком способе разлива напитков.
Значит, либо вторая, либо шестая бутылочка имеет экстремальный размер, и по условию 3 там не может быть яд. Тогда по условию 4 в обеих этих бутылочках может быть только вино. Поскольку Гермиона сделала вывод, что в самой маленькой бутылочке напиток, позволяющий идти вперед, то на месте 2 или 6 самая большая бутылочка (с вином). А по условию 1 в бутылочках 1 и 5 яд, что и требовалось определить.
Заметим также, что в этом случае возможна расстановка бутылок, при которой Гермиона могла сделать свои выводы. Из условия 2 она однозначно делает вывод, что бутылочка номер 7 дает идти назад. А среди оставшихся бутылочек 3 и 4 одна должна быть самой маленькой – в ней не может быть яд, значит, там зелье для прохода вперед.

Моя эстетическая оценка задачи 2 балла. 12.06.07.
Владислав Франк, предложивший эту задачу, получает 5 призовых баллов. За правильное решение и предложенное усовершенствование этой задачи Дмитрий Милосердов получает 7 призовых баллов. За правильное решение этой задачи Сергей Беляев, Андрей Богданов, Стас Грицюк, Анатолий Казмерчук, Константин Кноп, Иван Козначеев, Евгений Машеров, Олег Полубасов, Виктор Филимоненков получают по 5 призовых баллов. За частичное решение Алекс Кочарин получает 2 призовых балла.

Конкурсная задача №74 (6 баллов)
Вася и Петя поспорили.
Вася утверждает, что объем многогранника, все грани которого правильные многоугольники, а все 16 ребер имеют длину 1, больше единицы.
Петя же утверждает, что объем такого многогранника меньше единицы.
Кто из них прав?

Ответ: Есть многогранники с указанными свойствами как объема, большего 1, так и объема меньшего 1, обладающие указанными свойствами. Таким образом, ответ зависит от того, что имели в виду Петя и Вася (а также автор задачи :)).
Решение. Многогранник, составленный из куба со стороной 1 и правильной четырехгранной пирамиды с ребрами 1 (у него по 9 граней и вершин; его набор валентностей граней (4, 4, 4, 4, 4, 3, 3, 3, 3), набор валентностей вершин (4, 4, 4, 4, 4, 3, 3, 3, 3)) обладает указанными свойствами и, очевидно, имеет объем, больше 1.
Многогранником объема меньше 1 с указанными в условии свойствами является, например, такой. У него 10 граней, 8 вершин, набор валентностей граней (4, 4, 3, 3, 3, 3, 3, 3, 3, 3), набор валентностей вершин (4, 4, 4, 4, 4, 4, 4, 4). Две четырехугольные грани параллельны друг другу и повернуты друг относительно друга на 45 градусов. Каждая вершина четырехугольной грани соединяется с двумя соседними вершинами другой четырехугольной грани ребром длины 1. Представить его себе можно так: две правильные четырехугольные пирамиды со стороной ребра 1 разрезаны вдоль боковых ребер, и, раскрываясь в виде бутонов навстречу друг другу, смыкаются. Объем такого многогранника у меня получился равным 2^(1/4)*(1+2^(1/2))/3, что меньше 1, так как квадрат этого числа (4+18^(1/2))/9 очевидно, меньше 1.
Моя эстетическая оценка задачи: 3 балла. 4.09.07.
За правильное решение этой задачи Дмитрий Милосердов, Евгений Машеров, Олег Полубасов, Константин Кноп, Виктор Филимоненков и Владислав Франк получают по 6 призовых баллов.

Конкурсная задача №76 (8 баллов)
На какое наибольшее число частей могут разбивать n-мерное пространство 2n гиперплоскостей, имеющих общую точку?
Примечание: Гиперплоскостью называется плоскость, размерность которой на единицу меньше размерности пространства.

Ответ: на 2^(2n-1) части.
Решение. Пусть B(k; n) – наибольшее количество частей, на которые разбивают n-мерное пространство k гиперплоскостей, имеющих общую точку. Покажем, что, при очевидных краевых условиях: B(1; n) = 2; B(k; 1) = 2 (для k, начиная с 1) верна рекурсивная формула:
B(k; n) = B(k-1; n)+B(k-1; n-1)
Действительно, пусть проведены k-1 гиперплоскость через одну точку. Проводя k-тую гиперплоскость, мы увеличиваем число разбиений пространства на такое же число частей, на какое эта гиперплоскость разбивается k-1 гиперпрямыми пересечения с остальными k-1 гиперплоскостями (действительно, каждый такой кусок гиперплоскости делит еще на 2 части какой-то кусок разбиения пространства). Но количество разбиений пространства k-1 гиперплоскостью не превосходит B(k-1; n), причем этот максимум достижим. Количество разбиений гиперплоскости k-1 гиперпрямыми не превосходит B(k-1; n-1), и этот также максимум достижим. Таким образом, сумма этих количеств в максимуме дает искомое рекурсивное выражение для B(k; n).
Из этой формулы следует, что B(k; n) = 2*(Sum(s=0...n-1)C(s; k-1)) (суммирование по s от 0 до n биномиальных коэффициентов, т. е. количеств способов выбрать s предметов из k-1 предмета). Доказательство при данном n поведем индукцией по k и n.
База. B(1; n) = 2*C(0; 0) = 2 - верно. B(k; 1) = 2*C(0; 0) = 2 - верно.
Шаг. B(k; n) = B(k-1; n) + B(k-1; n-1) = (по предположению индукции) = 2*(Sum(s=0...n-1)C(s; k-2)) + 2*(Sum(s=0...n-2)C(s; k-2)) = 2*(С(0; k-2) + Sum(s=1...n-1)C(s; k-2)+ Sum(s=0...n-2)C(s; k-2)) = (в последней сумме увеличиваем индекс суммирования на 1 заменой t=s+1) = 2*(С(0; k-2) + Sum(s=1...n-1)C(s; k-2)+ Sum(t=1...n-1)C(t-1; k-2)) = (сворачиваем слагаемые последних сумм по рекурсивной формуле Паскаля для биномиальных коэффициентов, а так же меняем С(0; k-2) = 1 на С(0; k-1) = 1) = 2*(С(0; k-1) + Sum(s=1...n-1)C(s; k-1)) = 2*(Sum(s=0...n-1)C(s; k-1)).
Подставляя теперь k = 2n получим
B(2n; n) = 2*(Sum(s=0...n-1)C(s; 2n-1)) = (так как сумма половины биномиальных коэффициентов с одним вторым индексом (равным 2n-1) равна половине суммы всех коэффициентов (а эта сумма равна 2^(2n-1)) = 2*2^(2n-2) = 2^(2n-1)

Моя эстетическая оценка задачи: 4 балла. 08.09.07.
За правильное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 8 призовых баллов.

Конкурсная задача №78 (4 балла)
Квадрат разрезали на n квадратов. Сумма периметров этих квадратов оказалась в 3 раза больше периметра исходного квадрата. Конечно ли множество таких n, при которых возможна описанная ситуация?

Ответ: такое множество бесконечно.
Решение. Суммарный периметр полученных квадратов состоит из периметра исходного квадрата (каждая часть которого является частью стороны одного квадрата разбиения), и удвоенной длине линий разбиения (каждая часть которых является частью сторон двух квадратов разбиения). Таким образом, суммарная длина линий разбиения равна 1 периметру исходного квадрата.
Разобьем квадрат на 4 одинаковых квадрата двумя средними линиями общей длиной 1/2. Один из этих квадратов разобьем на 4 одинаковых квадрата двумя средними линиями общей длиной 1/4 и т.д. А на k-том шаге разобьем не один, а два маленьких квадрата, на четыре малюсеньких квадрата каждый. Сумма длин проведенных линий равна 1/2+1/4+...+1/2^(k-1)+2/2^k = 1. При этом получится n = 4+3*(k-2)+6 = 3k+4 квадрата, а так как k - любое натуральное число, начиная с 2, то возможно бесконечно много значений n.

Моя эстетическая оценка задачи; 4 балла. 24.09.07.
За правильное решение этой задачи Анатолий Казмерчук, Галина Крюкова, Олег Полубасов, Виктор Филимоненков и Владислав Франк получают по 4 призовых балла.

Конкурсная задача №80 (7 баллов)
Для произвольного треугольника обозначим через S0, S1, S2 и S3 площади исходного треугольника и треугольников, составленных соответственно из медиан, биссектрис и высот исходного треугольника (при условии, что эти треугольники существуют).
Могут ли числа S0, S1, S2 и S3 образовывать арифметическую прогрессию.
Примечания: 1. Прогрессию с нулевой разностью не предлагать. 2. Решая эту задачу, я прибегал к помощи математических пакетов.

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

2. Введем прямоугольную систему координат, положив вершины большей стороны в точках С(0; 0) и В(2; 0). Положение третьей вершины А(x; h), где можно считать что h >=0, x >= 1, будет определять треугольник с точностью до подобия. Учитывая соотношения между сторонами, можно сказать, что многообразие треугольников различных форм является областью G, ограниченной линиями:
x = 1 (т. е. b = c), h = 0, и окружностью b = 2 (т. е. b = a).

3. Для любого такого треугольника его площадь S0 равна h. Из элементарных геометрических соображений следует, что площадь S1 треугольника из медиан всегда равна 3/4*S0 = 3/4*h.
Введем в области G две функции Sb(А) = S2/S0 и Sh(А) = S3/S0 (определенных там, где треугольники из биссектрис и высот существуют). Функции Sb(A) и Sh(А), очевидно, являются непрерывными в области G.
Для решения задачи нужно доказать, что в G найдется точка А такая, что Sb(A) = 1/2, Sh(A) = 1/4.

4.Исследуем функцию Sh(А) для определения вида ее линии уровня Sh(A) = 1/4. Высоты в треугольнике, задаваемом точкой А(x; h) равны h; 2h/b; 2h/c. Для того, чтобы из них можно было построить треугольник, нужно выполнение неравенства треугольника:
h + 2h/b >=2h/c.
То есть областью определения функции Sh(А) является область G без куска, содержащего точку В и ограниченного кривой c = 2b/(2+b) (соединяющей точки с c = 1, b = 2 и b = -1+sqrt(5), c = 2-b на границах области G). Вдоль этой линии Sh(А) = 0.
Также Sh(А) = 0 (в пределе) вдоль всего участка границы области определения с h = 0 (так как площадь треугольника из высот в этом случае есть бесконечно малая более высокого порядка малости, чем h = S0).

5. Исследуем Sh(А) на остальной части границы области определения.
На прямой x = 1 b = c = sqrt(h^2+1). Подставляя эти выражения в формулы для высот, и применяя формулу Герона для вычисления S3, получим, что вдоль указанной прямой
Sh(A) = 1/4*sqrt(h^2*(15-h^2)/(h^2+1))
Легко проверяется, что эта величина возрастает на интервале 0 <= h <= sqrt(3).
Значение 1/4 на этой прямой Sh(A) принимает при h = 2-sqrt(3)
На окружности b = 2 значения двух высот равны h, третья удовлетворяет равенству (2h/c)^2+= 4-(c/2)^2, откуда 16h^2 = 16c^2-c^4. Используя формулу Герона, получим, что вдоль указанной окружности:
Sh(A) = 1/4*sqrt(h^2*(c^2-1)/c^2).
Эта величина также возрастает с ростом h.
Значение 1/4 на этой окружности Sh(A) принимает при h = 1.

6. При каждом фиксированном значении h величина Sh(A) убывает при движении A от прямой x = 1 к правой границе области определения Sh(A). Это проверяется прямым вычислением производной функции Sh(h, b) по b при фиксированном h (выражение для Sh(A) находится по формуле Герона).
Таким образом, для любого фиксированного h лежащего в пределах 2-sqrt(3) <= h <= 1 функция Sh(A) примет значение большее, чем 1/4 на левой границе области определения, и меньшее 1/4 на правой границе. Поскольку Sh(A) непрерывна в области определения, то, при движении А от левой границы области определения к правой, при фиксированном h найдется ровно одна точка, в которой Sh(A) = 1/4. При других значениях h таких точек нет.

7. Из пунктов 4-6 непосредственно следует, в области определения функция Sh(A) принимает значение 1/4 в точках M(1; 2-sqrt(3)) и N(sqrt(3); 1), а также на некоторой дуге MN (линия уровня Sh(A) = 1/4 является непрерывной линией, в силу непрерывности Sh(A), а то, что на этой линии не может быть петель следует из п. 6).

8. Вычисляя теперь значения функции Sb(A) в точках M и N, получим, что S(M) > 1/2, S(N) < 1/2. (Выражение для функция Sb(A) находится из формулы Герона и школьных формул, выражающих биссектрисы через стороны треугольников; поскольку точки M и N соответствуют равнобедренным треугольникам, эти формулы упрощаются – но я все равно не хочу здесь приводить конкретные расчеты).
На самом деле, вдоль линии уровня Sh(A) = 1/4 функция Sb(A) определена, и в силу непрерывности на ней найдется точка, где Sb(A) = 1/2. Это и будет нужное нам положение точки A.
Однако, вместо доказательства факта вхождения линии уровня Sh(A) = 1/4 в область определения функции Sb(A), легче допустить, что на этой линии Sb(A) определена не везде. Пусть тогда K – первая точка при движении от M по линии уровня, где Sb(K) не определена (то есть сумма двух биссектрис равна третьей). Но тогда в пределе Sb(K) = 0. А значит, в силу непрерывности Sb(A), на дуге MK все равно найдется точка, где Sb(A) = 1/2.

Моя эстетическая оценка задачи в процессе решения задачи вела себя гораздо более разрывно и менее монотонно, чем рассмотренные выше функции. Но в конце концов достигла 5 баллов, и на этом стабилизировалась. Красивый вопрос, требующий неочевидного решения.
А вот цена задачи, на мой взгляд, серьезно занижена. Например, по сравнению с последней задачей прошлого тура (про таблицы спортивных соревнований) она, на мой взгляд, сложнее, а стоит существенно меньше. 13.11.07.
За правильное решение этой задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов.
Итоги VIII-го тура
1. Виктоp Филимоненков 60
2. Анатолий Казмерчук 55
3. Владислав Фpанк 47
4. Олег Полубасов 45
4. Константин Кноп 45
6. Дмитpий Милосеpдов 23
7. Андpей Богданов 15
7. Евгений Машеpов 15
9. Сергей Беляев 14
10. Галина Крюкова 13
11. Иван Козначеев 9
12. Стас Гpицюк 6
12. Алекс Кочаpин 6
14. Дмитрий Бобровский 4
14. Сеpгей Аpакчеев 4
16. Ефим Подвойский 3
Tags: Задачи, Математика
Subscribe

  • Бессловесная игра

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

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

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

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

    Также в игре: Вопрос 191 (оно), Вопрос 192 (шаги и прыжки), Вопрос 193 (анаграммы), 194. (две строчки) Если к каждому их трех коротких слов…

  • 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