ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

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



Задача 109998

Темы:   [ Индукция (прочее) ]
[ Математическая логика (прочее) ]
[ Объединение, пересечение и разность множеств ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4
Классы: 7,8,9,10,11

В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.

Решение

Докажем утверждение индукцией по числу n учеников в классе. Для n=3 утверждение очевидно. Предположим, что оно верно при n N . Пусть n=N+1 . Утверждение верно, если в классе ровно один молчун. Пусть их не менее двух. Выделим молчуна A и его друзей – болтунов B1,..,Bk . Для оставшихся n-1-k учеников утверждение верно, т.е. можно выделить группу M , в которой каждый болтун дружит с нечетным числом молчунов и в M входит не менее учеников. Предположим, что болтуны B1,..,Bm дружат с нечетным числом молчунов из M , а Bm+1,..,Bk – с четным числом. Тогда, если m , то добавим к группе M болтунов B1,..,Bm , а если m< , то добавим к группе M болтунов Bm+1,..,Bk и молчуна A . В обоих случаях мы получим группу учеников, удовлетворяющую условию задачи.
Прислать комментарий


Задача 31374

Темы:   [ Индукция (прочее) ]
[ Комбинаторная геометрия (прочее) ]
Сложность: 4
Классы: 6,7,8,9

В городе 100 домов. Какое наибольшее число замкнутых непересекающихся заборов можно построить так, чтобы любые 2 забора ограничивали разные группы домов?

Решение

199 (если каждый забор что-то ограничивает). Указание: воспользуйтесь индукцией.

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


Задача 107981

Темы:   [ Индукция (прочее) ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 7,8,9

Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.

Комментарий. Словом мы называем любую последовательность букв русского алфавита, не обязательно осмысленную, подсловом называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.

Решение

Рассмотрим последовательность слов:

А, АБА, АБАВАБА, АБАВАБАГАБАВАБА, ...

Следующее слово получается из предыдущего так: пишется предыдущее слово, затем первая из букв, которых в нем нет, а затем это же слово еще раз.

Докажем методом полной индукции следующее утверждение: в n-м слове нет соседних одинаковых подслов, но если к нему приписать любую из первых n букв алфавита, то такие подслова появятся. Тогда 33-е слово является требуемым (в русском алфавите 33 буквы).

База индукции. Для n = 1 утверждение очевидно.

Шаг индукции. Пусть утверждение справедливо для всех слов с номерами от 1 до n - 1. Рассмотрим n-е слово. В нем n-я буква алфавита стоит в центре и разбивает слово на два одинаковых подслова, совпадающих с (n - 1)-м словом.

Если бы нашлись два соседних одинаковых подслова, то, по предположению индукции, они не могли бы располагаться оба в (n - 1)-м слове. Значит, одно из них содержит n-ю букву алфавита. Но эта буква только одна, и в соседнем подслове ее нет. Противоречие. Следовательно, в n-м слове тоже нет соседних одинаковых подслов.

Если приписать к n-му слову n-ю букву алфавита, то слово разобьется на два одинаковых подслова. Если приписать букву с номером k < n, то k-е слово, которое является началом и концом n-го слова, даст два соседних одинаковых подслова (по предположению индукции).

Комментарии. 1o. Длина искомого 33-го слова равна 233 - 1, что составляет примерно 10 миллиардов букв!

2o. Построенные слова играют важную роль в комбинаторике и теории полугрупп. Определим последовательность слов Zn равенствами: Z1 = x1; Zn + 1 = Znxn + 1Zn, где xi - переменные (вместо которых можно подставлять слова). Попытайтесь доказать, что при любом n в любой бесконечной последовательности букв конечного алфавита встретится слово вида Zn, где вместо x1, ..., xn подставлены некоторые слова. Например, встретится слово вида x1x2x1, где x1, x2 - слова.

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


Задача 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 лампочек. Обозначим необходимый для этого набор кнопок через Si. Если погасла и i-я, то индуктивный переход доказан. Значит, можно считать, что при любом i нажатие на кнопки набора Si приводит к следующей ситуации: горит только i-я лампочка.

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

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

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

x = (x1,..., xn),

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

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

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

(x1,..., xn) $\displaystyle \mapsto$ $\displaystyle \sum$xi,

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

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

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

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


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



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .