Страница: << 7 8 9 10 11 12 13 >> [Всего задач: 333]      

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

---

Задача 73617

Темы:   [ Индукция (прочее) ] [ Принцип крайнего ]

Сложность: 4+ Классы: 7,8,9

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

Решение

Наиболее бесхитростное доказательство — индукцией по числу n автомашин — проводится так. Случай n=1 очевиден. Предположим, что для n машин утверждени е доказано. Пусть машин n+1. Тогда среди них найдется такая машина A, которая может, пользуясь лишь имеющимся в ней бензином, доехать до следующей машины B (это легко доказывается "от противного") Выльем из машины B бензин в A, и уберем B с дороги. Среди оставшихся n машин, по предположению индукции, найдется такая, которая может объехать всю дорогу, забирая по пути бензин у остальных автомашин. Ясно, что та же машина может сделать это и в первоначальной ситуации, когда на дороге n+1 машина: на участке от A до B у нее заведомо хватит бензина (из машины A), а на остальных участках у нее ровно столько же бензина, сколько в случае n машин.

Многие читатели заметили, что задача сводится к такой:
По окружности выписано n чисел, сумма которых положительна; тогда найдется такое число, что оно само положительно, сумма его со следующим положительна, сумма со следующими двумя положительна и т.д. до суммы n-1 числа. (Достаточно около каждой машины написать число, равное разности между количеством имеющегося в ней бензина и количеством бензина, который нужен, чтобы доехать до следующей машины.) Эту задачу большинство читателей решали методом, описанным в книжке "Математические соревнования", ч.1 (Е.Б. Дынкин, С.А. Молчанов, А.Л. Розенталь. Математические соревнования. Арифметика и алгебра, "Наука", дополнительная серия "Библиотечки физико-математической школы" вып.3(*), 1970., задачи 76-77).

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

---

Задача 107789

Темы:   [ Индукция (прочее) ] [ Линейная и полилинейная алгебра ]

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

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

Решение

  Первый способ. Заметим, что результат нажатия нескольких кнопок не зависит от порядка их нажатия. Проведем индукцию по числу лампочек на табло. При n = 1 утверждение верно (так как найдется кнопка, соединенная с нечетным число лампочек, т. е. в точности с этой лампочкой).

Пусть утверждение доказано для n - 1 лампочек. Докажем утверждение для n лампочек. Рассмотрим i-ю лампочку. По предположению индукции, мы можем погасить остальные n - 1 лампочек. Обозначим необходимый для этого набор кнопок через S_i. Если погасла и i-я, то индуктивный переход доказан. Значит, можно считать, что при любом i нажатие на кнопки набора S_i приводит к следующей ситуации: горит только i-я лампочка.

Что произойдет, если при некотором состоянии табло нажать сначала кнопки из набора S_i, а потом кнопки из набора S_j? При этом изменится состояние ровно двух лампочек: лампочек с номерами i и j (подумайте, почему). Итак, мы научились менять состояние у любой пары лампочек.

По условию найдется кнопка T, соединенная с нечетным числом лампочек. Погасим все лампочки, кроме одной, соединенной с кнопкой T. Затем нажмем T. Тогда будет гореть четное число лампочек. Погасим их парами.

Второй способ. [с использованием линейной алгебры] Занумеруем лампочки числами от 1 до n. Поставим в соответствие состоянию табло строчку

где x_i = 1, если i-я лампочка горит, и x_i = 0 — если не горит. Такие наборы — это векторы n-мерного векторного пространства над полем из двух элементов.

Каждой кнопке мы тоже поставим в соответствие вектор a = (a₁,..., a_n), где a_i = 1, если i-я лампочка соединена с кнопкой, и a_i = 0, если не соединена. Ясно, что нажатие на кнопку переводит табло из состояния x в состояние a + x. Таким образом, наша задача состоит в том, чтобы доказать, что векторы, соответствующие кнопкам, порождают все векторное пространство.

Набору лампочек мы поставим в соответствие линейный функционал:

где сумма берется по всем i таким, что i-я лампочка входит в набор.

Все линейные функционалы получаются таким образом. Функционал обращается в нуль на векторе, соответствующем кнопке, тогда и только тогда, когда эта кнопка соединена с четным числом лампочек из этого набора. Значит, условие задачи переводится на язык линейной алгебры следующим образом: ни один функционал не обращается в нуль на всех кнопках. Но это равносильно тому, что система векторов, соответствующих кнопкам, полна! Такую равносильность часто называют альтернативой Фредгольма.

Комментарий. Назовем инвариантом такой набор лампочек, что любая кнопка меняет состояние только четного числа лампочек из этого набора. В условии задачи сказано, что таких инвариантов нет. Рассмотрим более общую ситуацию: пусть инварианты есть. Тогда, если множество первоначально горевших лампочек пересекается с некоторым инвариантом по нечетному числу лампочек, то все лампочки, очевидно, погасить не удастся.

Оказывается, что если множество первоначально горевших лампочек пересекается с любым инвариантом по четному числу лампочек, то все лампочки можно погасить. Данная задача является частным случаем этого утверждения. Это утверждение тоже можно доказать по индукции или при помощи линейной алгебры (попробуйте сделать это сами).

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

---

Задача 66477

Темы:   [ Индукция (прочее) ] [ Теория графов (прочее) ] [ Раскладки и разбиения ]

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

На олимпиаду пришло 2018 участников, некоторые из них знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют "кружок", если любой другой участник олимпиады не знаком с кем-то из них. Докажите, что можно рассадить всех участников олимпиады по 90 аудиториям так, что ни в какой аудитории не будут сидеть все представители какого-либо "кружка".

Решение

Докажем индукцией по k более общее утверждение: 2k аудиторий хватит для того, чтобы рассадить n ≤ k² участников. Тогда для получения утверждения задачи достаточно будет подставить k = 45 , поскольку 2018 ≤ 2025 = 45².

База k = 1, 2 . Поскольку 2k ≥ k² , мы можем посадить каждого участника в отдельную аудиторию.

Пусть утверждение доказано, когда количество участников не больше (k – 1)² . Докажем утверждение, когда количество участников не больше k² . Рассмотрим участника v c наибольшим числом d знакомых. Если d ≥ 2k – 2, то посадим v в одну аудиторию, всех его знакомых во вторую, а оставшихся n – 1 – d ≤ k² – 1 – (2k – 2) = (k – 1)² по предположению индукции мы можем рассадить в 2(k – 1) аудиторий так, что в этих аудиториях не будет "кружков". В первой аудитории только один человек, поэтому "кружков" там быть не может, во второй аудитории нет "кружков", так как там нет v, но он знаком со всеми из этой аудитории.

Если же d < 2(k – 1) , то заметим, что нам заведомо хватит d + 1 ≤ 2k аудиторий. Выделим d + 1 аудиторий и будем рассаживать участников по очереди так, чтобы никакие два знакомых не сидели в одной аудитории, тогда в одной аудитории не будут образовываться "кружки" (люди, сидящие в одной аудитории, не знакомы друг с другом). У каждого участника не больше чем d знакомых, так как аудиторий d + 1 , то всегда есть аудитория, где нет его друзей, куда мы его и посадим.

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

---

Задача 97781

Темы:   [ Индукция (прочее) ] [ Неравенство Коши ] [ Примеры и контрпримеры. Конструкции ]

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

а) Доказать, что для любых положительных чисел  x₁, x₂, ..., x_k  (k > 3)  выполняется неравенство:

б) Доказать, что это неравенство ни для какого  k > 3  нельзя усилить, то есть доказать, что для каждого фиксированного k нельзя заменить двойку в правой части на большее число так, чтобы полученное неравенство было справедливо для любого набора из k положительных чисел.

Решение

  а) Применим метод математической индукции. Проверим неравенство для  k = 4:

(Cм. задачу 30861.)
  Предположим, что для некоторого  k ≥ 4  неравенство доказано. Рассмотрим  k + 1  положительных чисел  x₁, x₂, ..., x_k, x_k+1.  Левая часть не меняется при циклической перестановке индексов, поэтому можно считать, что x_k+1 – наименьшее из всех чисел. Имеем:

  б) Положим,  x₁ = x₂ = 1,  x_i = ε^i–2  (i = 3, ..., k),  где ε – "достаточно малое" положительное число. Тогда первые два слагаемых меньше 1, каждое из
k – 2  остальных слагаемых меньше ε. Таким образом, левая часть меньше чем  2 + (k – 2)ε,  то есть может быть сколь угодно близка к 2.

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

---

Задача 60309

Темы:   [ Свойства модуля. Неравенство треугольника ] [ Индукция (прочее) ] [ Неравенства с модулями ]

Сложность: 2 Классы: 8

Докажите неравенство: |x₁ + ... + x_n| ≤ |x₁| + ... + |x_n|, где x₁,..., x_n — произвольные числа.

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

---

Страница: << 7 8 9 10 11 12 13 >> [Всего задач: 333]      

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