М1768. Аэробус

Задача из журнала «Квант» (2001 год, 5 выпуск)

Условие

а) Расположите первые 100 натуральных чисел в таком порядке, чтобы для любых нескольких (но не всех) из этих чисел сумма номеров занятых ими мест не равнялась сумме самих этих чисел.

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

Решение

а) Укажем два способа: 100, 1, 2, \ldots, 97, 98, 99 и 2, 3,4, \ldots, 99, 100, 1. Каждый из них дает требуемое расположение чисел, в чем легко непосредственно убедиться.

б) Ответ: 301 место.
Каждый пассажир включен в один из циклов вида P_{1}, P_{2}, \ldots , P_{m}, где P_{1}, P_{2}, \ldots , P_{m} – некоторые пассажиры, причем P_{i}-й пассажир (i =  1, 2, \ldots , m - 1) имеет билет на место, которое занимает P_{i+1}-й пассажир, а P_{m}-й пассажир – на место, которое занимает P_{1}-й пассажир. Если в таком цикле 100 пассажиров или менее, то все они могли составить одну рассматриваемую группу, для которой среднее арифметическое номеров занимаемых ими мест равно среднему арифметическому номеров мест, указанных в их билетах, что противоречит условию. Поэтому m \geq 101 + r \geq 202. Значит, если число циклов не меньше 3, то в аэробусе размещаются 303 или более пассажиров. Заметим далее, что если P_{k}, P_{k+1}, \ldots , P_{k+r} – цепочка пассажиров, последовательно включенных в некоторый цикл, причем номера билетов P_{k}-го и P_{k+r}-го отличаются на 1, то r \geq 101. Рассматривая цепочку P_{k+r}, P_{k+r+1} , \ldots , P_{m}, P_{1}, \ldots , P_{k}, получим неравенство m - (k + r) + k \geq 101. Следовательно, m \geq 101 + r \geq 202 , и поэтому число мест в аэробусе может быть меньшим, чем 303, только если выполняется одно из следующих условий:

  1. Все пассажиры включены в один цикл;
  2. Число циклов равно 2, причем любые два билета на соседние (по номерам) места принадлежат пассажирам из разных циклов.

Пусть выполнено первое условие. Рассмотрим пассажиров A_{n}, A_{n+1} и A_{n+2} с билетами на n-е, (n + 1)-е и (n + 2)-е места соответственно. Между A_{n}-м и A_{n+1}-м пассажирами в кратчайшей из цепочек, их соединяющих, имеется не менее 100 пассажиров, между A_{n+1}-м и A_{n+2}-м также не менее 100 пассажиров, а между A_{n+2}-м и A_{n}-м либо нет ни одного пассажира, либо имеется не менее 100. Значит, если общее число мест меньше 303, то либо A_{n} сидит на (n + 2)-м месте, либо A_{n+2} сидит на n-м месте. Ввиду произвольности номера n имеем (с точностью до направления) цикл A_{1} A_{3} A_{5} \ldots A_{N}A_{2}A_{4} \ldots A_{N'}, где N и N' – наибольший нечетный и наибольший четный номера соответственно, а A_{i}–пассажир, занимающий i-е место, i = 1, 2, \ldots, max ( N, N').Пассажиры, сидящие на местах N, 2, 4, \ldots , 198, имеют билеты на места 2, 4, 6,  \ldots , 200, а разность соответствующих средних равна (N - 200) : 100. Так как эта разность больше 1, получаем N \geq 301. Нетрудно убедиться, что цикл  A_{1}A_{3}A_{5} \ldots A_{301}A_{2}A_{4} \ldots A_{300} удовлетворяет условиям задачи. Пусть теперь выполнено второе условие, т.е. имеются два цикла, каждый из которых включает всех пассажиров с билетами на места одной четности. Если в каком-нибудь из этих циклов пассажир A_{n} сидит не на (n + 2)-м месте, а A_{n+2}– не на n-м месте, то в цикле не менее 202 пассажиров, а в аэробусе – не менее 403 мест. В противном же случае имеем (с точностью до направления) цикл A_{1}A_{3}A_{5} \ldots A_{N} , где пассажиры с билетами на места 1,3, 5, \ldots , 199 сидят на местах N, 1, 3, \ldots , 197; разность соответствующих средних арифметических  (N - 199) :100 больше 1, откуда N \geq 301.

С.Токарев

M567. О разбиении единичного отрезка на $p+q$ равных отрезков

Задача из журнала «Квант» (1979, №6)

Условие

Натуральные числа $p$ и $q$ взаимно просты. Отрезок $\left[ 0;1 \right]$ разбит на $p+q$ одинаковых отрезков (рис. $1$). Докажите, что в каждом из этих отрезков, кроме двух крайних, лежит ровно одно из $p+q-2$ чисел $\frac { 1 }{ p } , \frac { 2 }{ p }, \dots \frac { p-1 }{ p }, \frac { 1 }{ q }, \frac { 2 }{ q }, \dots \frac { q-1 }{ q }$.

567-1

Решение

Приведём два решения.

Первое решение. Из условия следует, что каждое из чисел $p$ и $q$ взаимно просто с числом $n=p+q$, поэтому никакие две из точек $\frac { i }{ p } ,\frac { j }{ q } ,\frac { k }{ n } $ (отличные от $0$ и $1$) не совпадают. Поскольку $\frac { 1 }{ p } >\frac { 1 }{ n } $ и $\frac { 1 }{ q } >\frac { 1 }{ n } $, любые две из точек $\frac { i }{ p } $ лежат в разных отрезках $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right] $ и любые две из точек $\frac { j }{ q } $ — тоже. Нужно лишь доказать, что какие-то две точки $\frac { i }{ p } $ и $\frac { j }{ q } $ не могут попасть в один и тот же отрезок $\left[ \frac { k }{ n } ;\frac { k+1 }{ n } \right]$ $\left( k=1,2,\dots,n-2 \right)$. Но это сразу следует из того, что дробь $\frac { k }{ n } =\frac { i+j }{ p+q } $ лежит между $\frac { i }{ p } $ и $\frac { j }{ q } $ (см., например, рисунок $2$: угловой коэффициент диагонали параллелограмма заключён между угловыми коэффициентами его сторон*).

M567-2

Второе решение. Нарисуем на клетчатой бумаге прямоугольник размерами $p\times q$ клеток и проведём в нём диагональ $OE$ (рис. $3$) — она и будет играть роль отрезка $\left[ 0;1 \right] $ нашей задачи. Линии одного направления (синие) делят её на $p$ равных частей, другого (красные) — на $q$ равных частей. Проведём через вершины клеток ещё ряд параллельных прямых — под углом $45^{\circ}$ к линиям сетки (на рисунке это — чёрные прямые $x+y=k$, где $k=1,2,\dots,p+q-1.$ Они делят $\left[ OE \right] $ на $n=p+q$ одинаковых отрезков. Утверждение задачи теперь становятся почти очевидным. В самом деле, на $\left[ OE \right] $ между любыми двумя сине-красными точками обязательно лежит чёрная точка: ведь, пересекая какую-то клетку, $\left[ OE \right] $ обязательно пересекает и её чёрную диагональ. (Можно вместо этого сказать и так: между любыми двумя точками пересечения $\left[ OE \right] $ с соседними чёрными прямыми лежит точка пересечения с синей или красной линией.)

В этом решении взаимная простота чисел $p$ и $q$ гарантирует, что $\left[ OE \right] $ не проходит через узлы сетки, отличные от $0$ и $E$ (глядя на наш маленький рисунок, в этом можно усомниться).

M567-3

Задача М567 допускает замечательное обобщение. Пусть $\alpha$ и $\beta $ — любые положительные числа, связанные соотношением $\frac { 1 }{ \alpha } +\frac { 1 }{ \beta } =1$. Отметим на числовой оси всевозможные числа вида $i\alpha $ и $j\beta \left( i\in Z,j\in Z \right)$. Тогда каждый отрезок $\left[ k;k+1 \right]$ оси $\left( k\in Z \right)$, ни в один из концов которого не попало отмеченное число, содержит ровно одно из отмеченных чисел $i\alpha$, $j\beta$. Наша задача эквивалента этому факту при рациональных $\alpha$ и $\beta$: нужно взять $\alpha =\frac { n }{ p } , \beta =\frac { n }{ q } $ (роль отрезка $\left[ 0;1 \right] $ будет играть теперь отрезок $\left[ 0;n \right])$. Этот же факт (для иррациональных $\alpha$ и $\beta$) упоминался недавно в решении задачи М538 («Квант», 1979, № $11$), очень похожем на наше второе решение М567.

Н.Васильев


(*) Тот факт, что «медианта» двух дробей $\frac { i }{ p }$ и $\frac { j }{ p }$ лежит между ними, использовался в статье «Близкие дроби» («Квант», 1975, №8).

M1412.Сумма дробей

Условие

Натуральные числа x и y таковы, что сумма дробей \frac { { x }^{ 2 }-1 }{ y\quad+\quad 1 } +\frac { { y }^{ 2 }-1 }{ x\quad+\quad 1 } — целое число. Докажите, что каждая из дробей — целое число.

Решение:

Пусть u — первая, v — вторая из этих дробей. Их сумма и произведение — целые числа, поэтому u и v корни квадратного уравнения с целыми коэффициентами, скажем, { z }^{ 2 } + m \cdot z + n = 0. Так как u и v — рациональные корни, то дискриминант { m }^{ 2 }-4\cdot n этого уравнения — рациональное число и, более того, целое, причем той же четности, что и m.
Формулы Виета
Но тогда u и v — тоже целые, ведь u, v = \frac { -m+-\sqrt { { m }^{ 2 }-4\cdot n } }{ 2 }, а в числителе под корнем стоит четное число. Существует также много решений этой задачи, связанных с рассмотрением общих делителей чисел x + 1 и y + 1.

А.Перлин

Существование иррациональных чисел

Натуральные, целые и рациональные числа

В процессе счёта возникли натуральные числа.
\mathbb{N}=\{1,2,3,...,n,...\}.
Сложение и умножение натуральных чисел снова даёт натуральное число. Операция «вычитание» во множестве натуральных чисел приводит к целым числам.
\mathbb{Z}=\{0,1,-1,2,-2,...,n,-n\}.
Операция «деление» во множестве целых чисел приводит к рациональным числам.
\mathbb{Q}=\{\frac{m}{n}, m\in\mathbb{Z}, n\in\mathbb{N}\}.
Например: \frac{1}{2}; \frac{5}{8}; -\frac{1}{2}; -\frac{11}{8}; -\frac{1}{30} ...
Во множестве рациональных чисел \mathbb{Q} выполняются все 4 арифметических действия. В данном множестве можно решать уравнения 1-ой степени (a*x+b=c), однако, простейшее уравнение x^2=a, a\in\mathbb{N} не всегда разрешимо в \mathbb{Q} , в частности, уравнение x^2=2 не имеет решений в \mathbb{Q} .
svg16

Необходимость иррациональных чисел

Докажем, что уравнение x^2=2 не имеет решений в \mathbb{Q} .

Теорема

Не существует рационального числа, квадрат которого равен 2.
\square  Предположим противное. Предположим, что существует такое рациональное число, квадрат которого равен 2. Числа p и q — числитель и знаменатель данного рационального числа; p и q — взаимно простые (числа, наибольший общий делитель которых равен 1).

\frac{p}{q}\in\mathbb{Q},   (\frac{p}{q})^{2}=2

p^{2}=2q^{2} \Rightarrow p^{2} \vdots 2

p^{2}  — чётное число, тогда p — чётное.

Отсюда: p=2s

4s^{2}=2q^{2} |:2

2s^{2}=q^{2} \Rightarrow q^{2}  — чётное \Rightarrow q  — чётное.

Получили противоречие того утверждения, что p и q — взаимно простые. \blacksquare

Таким образом, проблема решения уже таких уравнений приводит к необходимости расширения множества рациональных чисел путём добавления к ним иррациональных чисел.
Бесконечные дроби: периодические десятичные дроби
Зная рациональное число, его можно представить либо в виде конечной десятичной дроби, либо в виде бесконечной периодической десятичной дроби.

1) \frac{3}{8}=0,375 — конечная десятичная дробь;
0,375=\frac {375}{1000}=\frac {3}{8}.
2) \frac{27}{11}=2,454545...=2,(45) — бесконечная периодическая десятичная дробь.
2,(45)=2+\frac{45}{100}+\frac{45}{100^{2}}+\frac{45}{100^{3}}+\cdots =2+45(\frac{1}{100}+\frac{1}{100^{2}}+\frac{1}{100^{3}}+\cdots).
Используем формулу суммы бесконечно убывающей геометрической прогрессии:  S_{n}=\frac{b_{1}}{1-q}, где b_{1} — первый член геометрической прогрессии,  q — знаменатель прогрессии.
Получим: 2+45(\frac{1}{100}+\frac{1}{100^{2}}+\frac{1}{100^{3}}+\cdots)= 2+45*\frac{\frac{1}{100}}{1-\frac{1}{100}}=
=2+\frac{45}{99}=2\frac{5}{11} .
Договоримся, конечную десятичную дробь будем отождествлять с бесконечной десятичной дробью с "0" в периоде.
0,375=0,375(0).
Между множеством множеством всех рациональных чисел и множеством всех периодических бесконечных десятичных дробей установлена связь, если отождествлять бесконечную периодическую дробь с (9) с бесконечной периодической периодической дробью с (0).
2,5=2,5(0)=2,4+0,1=2,4+\frac{1}{10}= 2,4+(\frac{9}{100}+\frac{9}{1000}+\frac{9}{10000}+\cdots)= =2,4+\frac{9}{10}(\frac{1}{10}+\frac{1}{10^{2}}+\frac{1}{10^{3}}+\cdots) 2,4+0,9(9)=2,4(9).

Тест "Существование иррациональных чисел".

Тестовые задания по вышеизложенной теме.

Источники:

  1. З. М. Лысенко.  Лекции по математическому анализу.
  2. В. И. Коляда, А.А.Кореновский «Курс лекций по мат.анализу, часть 1» (Одесса, «Астропринт», 2009г.), стр.1.
  3. В. И. Ильин, Э.Г.Позняк «Основы мат.анализа, часть 1, выпуск 2» (Издание четвёртое, переработанное и дополненное, 1982г.) стр.40. (скачать учебник можно здесь).

Подробнее про «существование иррациональных чисел» на:

Wikipedia

Викизнание