На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
(с) Квант для младших школьников за какой-то древний год.
Здравствуйте, Apapa, Вы писали:
A>На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Если вокруг всех рационально-численных точек закрасить окрестности любого наперед заданного радиуса, то мы тем самым закрасим все пространство.
Доказательство:
Для любого наперед заданного радиуса r
Найдем целое число M > ] 1/(r*sqrt(D)) [, где D — размерность пространства (для плоскости D=2)
Очевидно, что точки (i/M, j/M ...) — имеют рациональные координаты.
Квадратная (кубическая, гиперкубическая) сетка из этих точек
имеет главную диагональ равную sqrt(M^2 * D) > r
Поэтому круглые (сферические...) окресности каждого узла сетки с огромным нахлестом захватывают всех соседей по сетке.
A>(с) Квант для младших школьников за какой-то древний год.
Привет, Кодт!
К>Здравствуйте, Apapa, Вы писали:
A>На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
К>Если вокруг всех рационально-численных точек закрасить окрестности любого наперед заданного радиуса, то мы тем самым закрасим все пространство.
К>Доказательство: К>Для любого наперед заданного радиуса r К>Найдем целое число M > ] 1/(r*sqrt(D)) [, где D — размерность пространства (для плоскости D=2) К>Очевидно, что точки (i/M, j/M ...) — имеют рациональные координаты. К>Квадратная (кубическая, гиперкубическая) сетка из этих точек К>имеет главную диагональ равную sqrt(M^2 * D) > r К>Поэтому круглые (сферические...) окресности каждого узла сетки с огромным нахлестом захватывают всех соседей по сетке.
A>(с) Квант для младших школьников за какой-то древний год. К>
Ну, хорошо... Ладно, ладно!
Тогда так (чуть-чуть посложнее).
На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Здравствуйте, Apapa, Вы писали:
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Рассмотрим квадратную сетку. Спроецируем на ось X точки пересечения луча с X-линиями.
Получим множество точек, с шагом S = ctg(alpha), где alpha — угол наклона луча к OX.
Задача сводится к эквивалентной:
доказать, что для любых наперед заданных S и r найдется k такое, что frac(k*S) < r
Исключим из S целую часть, s = frac(S)
frac(k*s) < к
Здравствуйте, Apapa, Вы писали:
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Вопрос — а зачем вводить объемность там где одна ни к чему? Если заменить "стоят столбики" на "нарисованы круги", то не то же самое?
Здравствуйте, Apapa, Вы писали:
A>Тогда так (чуть-чуть посложнее).
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Не снижая общности рассмотрим луч y = Ax (с лучем y = 0 все очевидно)
Если A рациональное => A = a1 / a2 => Луч проходит через точку (a2, a1) или (-a2, -a1)
Если A иррациональное:
Существует N такое, что 1/N < r
Рассмотрим точки пересечения луча с вертикальными линиями сетки: Y(i) = A*i
Обозначим через Y'(i) дробную часть Y(i), Y(i) = M(i) + Y'(i) где M(i) — целая часть
В последовательности Y'(i) все члены различны (если нет, Y'(i1) = Y'(i2) => A*i1 — M(i1) = A*i2 — M(i2) => A = (M(i1) — M(i2)) / (i1 — i2) — )
Рассмотрим первые N членов последователности Y'. Среди них существуют два такие, что i2 > i1, Y'(i1) — Y'(i2) = delta, abs(delta) < 1/N
Рассмотрим последовательность Z(i) = Y'(i1) + i * delta
Z(i) = MZ(i) + Z'(i) — целая и дробная части
Z — это арифметическая последовательность с шагом delta < 1/N, delta > 0 , поэтому в ней найдется член Z(i') такой, что Z'(i') < 1/N
Но Z'(i) = Y'(i1 + i * (i2-i1)), поэтому и в последовательности Y' найдется член Y'(i''), меньший 1/N
Тогда наш луч проходит через цилиндр точки (i'', M(i'')) ч.т.д.
Для средних школьников?
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Поскольку (по первой задаче) луч проходит мимо некой точки с рациональными координатами
(x = a/b, y = c/d) на расстоянии не более r` = r/bd, то (промасштабировав картинку на bd) он пройдёт мимо точки с целыми координатами (x = ad, y = cb) на (заданном) расстоянии r (r` * bd).
PS. Для решения первой задачи, достаточно показать, что на прямой, в окрестности любой рациональной точки есть другая рациональная точка на расстоянии меньше r. Это очевидно, так как для любого r есть рациональное число меньшее r, а сумма двух рациональных — рациональна. (Это чтоб не мучится с вычислением расстояний между точками в N-мерном пространстве, т.е. оперировать с кубиками, вписаными в исходные столбики (сферы) ).
...
A>Ну, хорошо... Ладно, ладно!
A>Тогда так (чуть-чуть посложнее).
...
Вспомнил! Очень похожая задачка, только ещё чуть посложнее.
Все знают параметрическое уравнение эллипса на плоскости, оси которого параллельны осям координат, а центр в точке (0,0). (Никаких формул не привожу, иначе все сразу догадаются как решать). Будем называть такой эллипс — квадратичным эллипсоидом или эллипсоидом степени 2.
По аналогии будем рассматривать кубические и д.т. эллипсоиды, т.е. те, у которых в уравнении стоят степени больше 2.
Требуется доказать, что если в уравнении этих эллипсоидов все коэффициенты — рациональны, то сами эллипсоиды нигде не проходят через точки с рациональными координатами, кроме, естественно, в точках пересечения с осями координат.
(Подсказка 1: Взято у Кнута "Исскуство программирования" )
(Подсказка 2: Задачка, имхо, довольно известная )
(Подсказка 3: )
Привет, mrhru!
M>Требуется доказать, что если в уравнении этих эллипсоидов все коэффициенты — рациональны, то сами эллипсоиды нигде не проходят через точки с рациональными координатами, кроме, естественно, в точках пересечения с осями координат.
Почему? Эллипсоид p^n/2 * x^n + q^n/2 * y^n = 1 проходит через точку (1/p; 1/q).
Или ты имел в виду уравнения вида (px)^n + (qx)^n = 1?
Тогда (0.2x)^2 + (0.2y)^2 = 1 проходит через точку (3; 4).
А над старшими степенями надо подумать!
Здравствуйте, Apapa, Вы писали:
A>Привет, mrhru!
M>>Требуется доказать, что если в уравнении этих эллипсоидов все коэффициенты — рациональны, то сами эллипсоиды нигде не проходят через точки с рациональными координатами, кроме, естественно, в точках пересечения с осями координат.
A>Почему? Эллипсоид p^n/2 * x^n + q^n/2 * y^n = 1 проходит через точку (1/p; 1/q).
A>Или ты имел в виду уравнения вида (px)^n + (qx)^n = 1? A>Тогда (0.2x)^2 + (0.2y)^2 = 1 проходит через точку (3; 4). A>А над старшими степенями надо подумать!
Здравствуйте, LCR, Вы писали:
LCR>Здравствуйте, mrhru, Вы писали:
M>>Да, именно над старшими степенями.
LCR>Используем результат Великой теоремы Ферма: уравнение x^n+y^n=z^n не имеет целочисленных решений для n>2.
LCR>Дальше продолжать?
Раскусили.
(PS. Эта задачка действительно приводится у Кнута, только в стандартной форме, и во всех трёх томах. Сложность он её установил 45 единиц (50 единиц у него имеют те задачки, решение которых неизвестно). Это в третьем издании, а во втором эта задача имела честные 50 баллов. )
Здравствуйте, mrhru, Вы писали:
M>(PS. Эта задачка действительно приводится у Кнута, только в стандартной форме, и во всех трёх томах. Сложность он её установил 45 единиц (50 единиц у него имеют те задачки, решение которых неизвестно). Это в третьем издании, а во втором эта задача имела честные 50 баллов. )
Здравствуйте, LCR, Вы писали:
LCR>Здравствуйте, mrhru, Вы писали:
M>>(PS. Эта задачка действительно приводится у Кнута, только в стандартной форме, и во всех трёх томах. Сложность он её установил 45 единиц (50 единиц у него имеют те задачки, решение которых неизвестно). Это в третьем издании, а во втором эта задача имела честные 50 баллов. )
LCR>Э-ээ. а где там баллы?
Там это где?
Если у Кнута, то он "быллы" называет рейтингом. Сама задача, например: том 2, стр.25, под номером 4.
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Т.к. я слегка опоздал со своим доказательством, то сперва небольшое предисловие:
Доказательство mrhru
, имхо, неверно, т.к. у нас не фиксированы знаменатели (b и d) рациональных чисел, а их увеличение может "съесть" весь эффект масштабирования.
Доказательство nikholas
использует классическое доказательство теоремы Дирихле, а мне казалось, что для школьников должно существовать, что-нибудь попроще.
В итоге я придумал такое доказательство:
Параллельно перенесем луч на 1 по оси y, т.е. в точку с координатами (0, 1). И рассмотри полосу заключенную между двумя лучами. Проведем вертикальную прямую из точки с целой координатой M на оси x. Данная прямая отсечет от полосы параллелограмм. Если исходная прямая не проходит через узлы целочисленной сетки, а именно такие прямые нас и интересуют, то внутри этого параллелограмма окажется ровно M целочисленных точек.
Теперь разрежем параллелограмм на M одинаковых полосок прямыми параллельными исходной и посмотрим как эти M целочисленных точек распределены по полоскам. Если в полоске прилегающей к исходной прямой лежит хотя бы одна точка, то значит существует целочисленная точка отстоящая от прямой на расстояние <= 1/M. Предположим, что такой точки не существует, тогда в одной из полосок у нас окажется как минимум две точки. Перенесем начало исходного луча в ближайшую из этих точек. Очевидно, что от этого переноса ничего не изменится, но вторая точка будет отстоять от луча на расстоянии <= 1/M. Таким образом мы доказали, что для любого целого M найдется целочисленная точка, отстоящая от луча на растояние <= 1/M. Осталось выбрать M > 1/r и утверждение доказано.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Apapa, Вы писали:
MP> A>>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
MP>Т.к. я слегка опоздал со своим доказательством, то сперва небольшое предисловие: MP>Доказательство mrhru
, имхо, неверно, т.к. у нас не фиксированы знаменатели (b и d) рациональных чисел, а их увеличение может "съесть" весь эффект масштабирования.
Извиняюсь, я немного посопротивляюсь.
Из решения первой задачи, известно, что существует как минимум одна точка с рациональными координатами, мимо которой луч проходит на некотором расстоянии r` (произвольном, но наперед заданном). Зафиксируем её . Мастабирование всей картины меняет только координаты точки и расстояние до луча, причём строго пропорционально. Собственно говоря, меряли мы в дюймах, а потом назвали дюймы метрами. Наклон самого луча нисколько не изменится.
Теперь масштам мы можем выбрать таким, что значенатели координат точки станут равны 1, т.е. сами координаты будут уже целочисленными.
MP>Доказательство nikholas
использует классическое доказательство теоремы Дирихле, а мне казалось, что для школьников должно существовать, что-нибудь попроще. MP>В итоге я придумал такое доказательство:
Здравствуйте, mrhru, Вы писали:
M>Извиняюсь, я немного посопротивляюсь. M>Из решения первой задачи, известно, что существует как минимум одна точка с рациональными координатами, мимо которой луч проходит на некотором расстоянии r` (произвольном, но наперед заданном). Зафиксируем её . Мастабирование всей картины меняет только координаты точки и расстояние до луча, причём строго пропорционально. Собственно говоря, меряли мы в дюймах, а потом назвали дюймы метрами. Наклон самого луча нисколько не изменится. M>Теперь масштам мы можем выбрать таким, что значенатели координат точки станут равны 1, т.е. сами координаты будут уже целочисленными.
Из решения первой задачи следует, что знаменатель O(1/r), после масштабирования на знаменатель, получаем, что расстояние до целочисленной точки O(1).
Т.е. минимальное расстояние должно убывать быстрее чем 1/знаменатель. Поэтому и приходится тем или иным способом доказывать теорему Дирихле, которая дает 1/знаменатель^2.
Привет, MichaelP!
MP>Параллельно перенесем луч на 1 по оси y, т.е. в точку с координатами (0, 1). И рассмотри полосу заключенную между двумя лучами. Проведем вертикальную прямую из точки с целой координатой M на оси x. Данная прямая отсечет от полосы параллелограмм. Если исходная прямая не проходит через узлы целочисленной сетки, а именно такие прямые нас и интересуют, то внутри этого параллелограмма окажется ровно M целочисленных точек. MP>Теперь разрежем параллелограмм на M одинаковых полосок прямыми параллельными исходной и посмотрим как эти M целочисленных точек распределены по полоскам. Если в полоске прилегающей к исходной прямой лежит хотя бы одна точка, то значит существует целочисленная точка отстоящая от прямой на расстояние <= 1/M. Предположим, что такой точки не существует, тогда в одной из полосок у нас окажется как минимум две точки. Перенесем начало исходного луча в ближайшую из этих точек. Очевидно, что от этого переноса ничего не изменится, но вторая точка будет отстоять от луча на расстоянии <= 1/M. Таким образом мы доказали, что для любого целого M найдется целочисленная точка, отстоящая от луча на растояние <= 1/M. Осталось выбрать M > 1/r и утверждение доказано.
И ни одной дроби, ни одного умножения или деления! Ну хотя бы сложил чего-нибудь!
MP>P.S. Имхо, вполне по силам средним школьникам.
Я точно помню, что задачка для младших школьников, но видимо продвинутых!
Лирическое отступление...
Необходимо и достаточно доказать для вертикальных отрезков длины 2/N.
Пусть это не так. Тогда для любого p/q тангенс угла наклона (вертикальный случай очевиден) не попадает на отрезок p/q+-1/qN.
Кажется в Зориче была такая задачка, что для любого числа x есть p/q из Q не дальше, чем 1/qN, где N задано.
Другими словами, если вокруг каждой рациональной точки p/q описать интервал 1/qN, где N задано, то покроется вся прямая. Этим задачка и сложнее, по сравнению с предыдущей. Там требовалось покрытие интервалами фиксированной длины, что очевидно покрывает всю прямую.
Вот тебе и для "младших школьников". Надо Зоричу сообщить решение MichaelP его задачки! Вот он порадуется!
Здравствуйте, MichaelP, Вы писали:
MP>Из решения первой задачи следует, что знаменатель O(1/r), после масштабирования на знаменатель, получаем, что расстояние до целочисленной точки O(1). MP>Т.е. минимальное расстояние должно убывать быстрее чем 1/знаменатель. Поэтому и приходится тем или иным способом доказывать теорему Дирихле, которая дает 1/знаменатель^2.
Спасибо. Т.е. из существования рациональной точки вблизи другой рациональной точки на расстоянии 1/r напрямую не следует существование другой рациональной точки на расстоянии 1/r^2. Так?
И для этого следует "тем или иным способом доказывать теорему Дирихле"?
Apapa.gif)
Перекуём баги на фичи!
)
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Тоже хорошее доказательство!
