Страница: << 1 2 3 4 5 >> [Всего задач: 24]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 109675  (#98.5.10.8)

Темы:   [ Числовые таблицы и их свойства ] [ Индукция (прочее) ] [ Симметрия и инволютивные преобразования ]

Сложность: 5 Классы: 8,9,10,11

В каждую клетку квадратной таблицы размера  (2ⁿ – 1)×(2ⁿ – 1)  ставится одно из чисел 1 или – 1. Расстановку чисел назовём удачной, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.

Решение

  Пусть R – удачная расстановка в таблице (2ⁿ – 1)×(2ⁿ – 1). Расставим числа на клетчатой плоскости, как показано на рисунке слева (симметрия буквы R означает, что там стоит таблица R, отраженная соответствующим образом). Тогда расстановка на всей плоскости удачна (то есть любое число есть произведение его четырёх соседей) и, кроме того, она 2ⁿ⁺¹-периодична, то есть при сдвиге на 2ⁿ⁺¹ вверх или вправо она переходит в себя.

  Докажем индукцией по n, что любая 2ⁿ-периодичная перестановка состоит из единиц.
  База  (n = 0)  очевидна:  a = a⁴,  где a – число в клетке.
  Шаг индукции. Пусть  n ≥ 1.  Рассмотрим фрагмент таблицы, показанный на рисунке справа.
  Имеем:  a₂₃ = a₁₃a₂₂a₂₄a₃₃,  a₃₂ = a₂₂a₃₁a₃₃a₄₂,  a₃₄ = a₂₄a₃₃a₃₅a₄₄,  a₄₃ = a₃₃a₄₂a₄₄a₅₃,  откуда
  то есть то же соотношение верно для "разрежённой" таблицы, состоящей из чисел, находящихся в пересечениях нечётных строк с нечётными столбцами. Эта таблица 2^n–1-периодична, поэтому по предположению индукции она состоит из единиц. Аналогично остальные три "разрежённых" подтаблицы состоят из единиц, что и требовалось.

Ответ

Удачная расстановка единственна – все числа равны единице.

Прислать комментарий

---

Задача 109668  (#98.5.11.1)

Темы:   [ Теорема Виета ] [ Графики и ГМТ на координатной плоскости ] [ Кубические многочлены ]

Сложность: 4- Классы: 9,10,11

Прямые, параллельные оси Ox, пересекают график функции  y = ax³ + bx² + cx + d:  первая – в точках A, D и E, вторая – в точках B, C и F (см. рис.). Докажите, что длина проекции дуги CD на ось Ox равна сумме длин проекций дуг AB и EF.

Решение

Из рисунка видно, что  a > 0.  Если  y = p  и  y = q  – уравнения заданных прямых, то абсциссы точек A, D и E – корни  x₁ < x₂ < x₃  уравнения
ax³ + bx² + cx + d – p = 0,  а точек B, C и F – корни  X₁ < X₂ < X₃  уравнения  aX³ + bX² + cX + d – q = 0.  По теореме Виета  x₁ + x₂ + x₃ = X₁ + X₂ + X₃.  Отсюда  x₂ – X₂ = (X₁ – x₁) + (X₃ – x₃),  что и требовалось.

Прислать комментарий

---

Задача 109661  (#98.5.11.2)

Темы:   [ Три прямые, пересекающиеся в одной точке ] [ Вписанные и описанные окружности ] [ Гомотетия помогает решить задачу ] [ Трапеции (прочее) ]

Сложность: 4- Классы: 9,10,11

Окружность, вписанная в треугольник ABC, касается сторон BC, CA, AB в точках A₁, B₁, C₁ соответственно. Точки A₂, B₂, C₂ – середины дуг BAC, CBA, ACB описанной окружности треугольника ABC. Докажите, что прямые A₁A₂, B₁B₂ и C₁C₂ пересекаются в одной точке.

Решение

  Касательная l_A в точке A₂ к описанной окружности параллельна BC. Рассмотрев касательные l_B, l_C в точках B₂, C₂, аналогично получим:  l_B || AC,  l_C || AB.   Поэтому треугольник ABC гомотетичен треугольнику, образованному прямыми l_A, l_B, l_C. При этой гомотетии A₁ переходит в A₂, B₁ – в B₂, C₁ – в C₂. Следовательно, прямые A₁A₂, B₁B₂, C₁C₂ пересекутся в центре гомотетии.

Прислать комментарий

---

Задача 109662  (#98.5.11.3)

Темы:   [ Свойства параллельного переноса ] [ Метод ГМТ ] [ Правильный (равносторонний) треугольник ] [ Выпуклая оболочка и опорные прямые (плоскости) ]

Сложность: 5- Классы: 9,10,11

На плоскости нарисовано некоторое семейство S правильных треугольников, получающихся друг из друга параллельными переносами, причем любые два треугольника пересекаются. Докажите, что найдутся три точки такие, что любой треугольник семейства S содержит хотя бы одну из них.

Решение

Пусть ABC – один из треугольников семейства S . Его высоту примем за единицу. Так как треугольники из S попарно пересекаются, то они лежат в некоторой полосе ширины 2, параллельной стороне AB . Аналогично, взяв полосы, параллельные BC и CA , рассмотрим их пересечение– это будет шестиугольник H с углами по 120^o и расстояниями между противоположными сторонами, равными 2. У такого шестиугольника длины сторон чередуются, обозначим их a и b (см. рис. 1) .
Пусть вначале a b , тогда все треугольники из S содержат центр фигуры H (см. рис. 1) .

                     
Рис. 1                  Рис. 2                  Рис. 3
Если же a>b , то рассмотрим прямые l_X , l_Y , l_Z , параллельные сторонам шестиугольника и равноудаленные от них. В качестве искомых точек X , Y и Z возьмем середины отрезков, высекаемых сторонами на этих прямых (см. рис. 2) . Покажем, что любой треугольник T , T S , содержит какую-то точку из множества M={X,Y,Z} . Заметим, что T пересекает любую из прямых l_X , l_Y и l_Z (см. рис. 2) , так как иначе T лежит в полосе меньшей ширины, чем его высота. Предположим противное: T не содержит точек X , Y или Z , тогда без ограничения общности можно считать, что T пересекает l_X выше и левее X , а l_Y – левее Y (см. рис. 3) . Так как TΔ XYZ , то легко видеть, что правая нижняя вершина T лежит в Δ XYZ , а значит, T не пересекает l_Z – противоречие.

Прислать комментарий

---

Задача 109663  (#98.5.11.4)

Темы:   [ Связность и разложение на связные компоненты ] [ Степень вершины ] [ Метод спуска ]

Сложность: 5 Классы: 9,10,11

В стране N  1998 городов, и из каждого осуществляются беспосадочные перелеты в три других города (все авиарейсы двусторонние). Известно, что из каждого города, сделав несколько пересадок, можно долететь до любого другого. Министерство Безопасности хочет объявить закрытыми 200 городов, никакие два из которых не соединены авиалинией. Докажите, что это можно сделать так, чтобы можно было долететь из каждого незакрытого города в любой другой, не делая пересадок в закрытых городах.

Решение

  Рассмотрим граф, вершинами которого являются города, рёбрами – авиалинии. Получится связный граф, степени вершин которого равны 3.
  Предположим, что в этом графе есть два пересекающихся (по вершине) цикла (см. рис.). Рассмотрим вершину O, в которой они разветвляются. Эта вершина, очевидно, имеет степень 3. Удалим её и три выходящих из неё ребра OA, OB, OC. При этом граф сохранит связность, так как существует путь, соединяющий вершины A, B и C.

  Рассмотрим полученный граф. Если в нём есть два пересекающихся цикла, то повторим операцию. И так далее. Заметим, что никакие две удалённые вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени 3, а после каждой операции степени вершин, соседних с удалённой, уменьшались, то есть они не могут стать равными 3.

  Лемма. В связном графе с n вершинами и не менее чем  ⁴ⁿ/₃  рёбрами есть два пересекающихся цикла.
  Доказательство. Предположим, что это не так. В силу связности графа, в нём можно выделить дерево с n вершинами. Будем возвращать в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает количество циклов по крайней мере на один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трёх вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно  n – 1  ребро. Следовательно, рёбер не более, чем  (n – 1) + ⁿ/₃ < ⁴ⁿ/₃.  Противоречие.

  Пусть  N = 1998  – количество вершин в исходном графе, тогда исходное количество рёбер равно ^3N/₂. За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество рёбер – на три. Предположим, что было сделано x операций. Тогда стало  N – x  вершин и  ^3N/₂ – 3x  рёбер. До тех пор, пока выполняется неравенство  ^3N/₂ – 3x ≥ ⁴/₃ (N – x)  вершины удалять можно. Решив это неравенство, получаем  x ≤ ^N/₁₀, то есть можно удалить  [¹⁹⁹⁸/₁₀] + 1 = 200  вершин, что и требовалось.

Прислать комментарий

---

Страница: << 1 2 3 4 5 >> [Всего задач: 24]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями