На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса 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. Так?
И для этого следует "тем или иным способом доказывать теорему Дирихле"?
Здравствуйте, mrhru, Вы писали:
M>Спасибо. Т.е. из существования рациональной точки вблизи другой рациональной точки на расстоянии 1/r напрямую не следует существование другой рациональной точки на расстоянии 1/r^2. Так? M>И для этого следует "тем или иным способом доказывать теорему Дирихле"?
Попробую пояснить на примере:
Расмотрим не целочисленные точки а "полуцелочисленные" по одной из координат, т.е. точки с координатами (0, 1/2) (0, 3/2) (1, 1/2) и т.д.
Повторим доказательство:
Поскольку (по первой задаче) луч проходит мимо некой точки с рациональными координатами
(x = a/M, y = c/M) на расстоянии не более r` = r/M, без ограничения общности мы можем выбрать рациональные координаты так, чтобы c и M были нечетными, а a четным, просто взяв вдвое более частую сетку из первого решения.
Промасштабировав картинку на M/2 он пройдёт мимо точки с координатами (x = a/2, y = c/2) на (заданном) расстоянии r (r`* M). Данная точка попадает на нашу сетку. Вроде бы доказано.
А теперь расмотрим луч выходящий из начала координат под углом 45 градусов. Очевидно, что он не приблизится к точкам сетки ближе чем на 1/sqrt(2)!
Этот эффект я и имел ввиду, когда говорил об O(1) для расстояний при масштабировании.
Здравствуйте, MichaelP, Вы писали:
MP>Попробую пояснить на примере:
Спасибо за недюжинное терпение , тем не менее продолжаю проявлять недюжинное непонимание.
MP>Расмотрим не целочисленные точки а "полуцелочисленные" по одной из координат, т.е. точки с координатами (0, 1/2) (0, 3/2) (1, 1/2) и т.д.
MP>Повторим доказательство: MP>Поскольку (по первой задаче) луч проходит мимо некой точки с рациональными координатами MP>(x = a/M, y = c/M) на расстоянии не более r` = r/M, без ограничения общности мы можем выбрать рациональные координаты так, чтобы c и M были нечетными, а a четным, просто взяв вдвое более частую сетку из первого решения.
"без ограничения общности" — уже не понятно, если это уже не справедливо для луча под 45 градусов.
MP>Промасштабировав картинку на M/2 он пройдёт мимо точки с координатами (x = a/2, y = c/2) на (заданном) расстоянии r (r`* M). Данная точка попадает на нашу сетку. Вроде бы доказано.
MP>А теперь расмотрим луч выходящий из начала координат под углом 45 градусов. Очевидно, что он не приблизится к точкам сетки ближе чем на 1/sqrt(2)!
MP>Этот эффект я и имел ввиду, когда говорил об O(1) для расстояний при масштабировании.
При выбранных выше "получисленных" точках так и выходит. А что мешает выбрать другие точки?
Я понимаю, O(1) слишком "большое" для доказанного ранее утверждения с оценкой O(1/r).
Зайдём по другому. Первоначальную задачу переформулируем чуть по другому: радиус столбиков примем не 1/r, а 1/r^2. В таком виде она имеет решение? Представляется, что имеет. Теми же самыми приёмами. И честно говоря, я не вижу какой либо "неустойчивости" или "незаконности" такого же решения при r -> inf.
Только если есть какие-то основания полагать, что если некоторое утверждение А справедливо для рациональных чисел и неком r -> inf, то это утверждение несправедливо или требует специального доказательства для случая r = r`^2, где r` -> inf.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Apapa, Вы писали:
MP> A>>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
использует классическое доказательство теоремы Дирихле, а мне казалось, что для школьников должно существовать, что-нибудь попроще.
Сам придумал, мамой клянусь MP>В итоге я придумал такое доказательство:
MP>Параллельно перенесем луч на 1 по оси y, т.е. в точку с координатами (0, 1). И рассмотри полосу заключенную между двумя лучами. Проведем вертикальную прямую из точки с целой координатой M на оси x. Данная прямая отсечет от полосы параллелограмм. Если исходная прямая не проходит через узлы целочисленной сетки, а именно такие прямые нас и интересуют, то внутри этого параллелограмма окажется ровно M целочисленных точек. MP>Теперь разрежем параллелограмм на M одинаковых полосок прямыми параллельными исходной и посмотрим как эти M целочисленных точек распределены по полоскам. Если в полоске прилегающей к исходной прямой лежит хотя бы одна точка, то значит существует целочисленная точка отстоящая от прямой на расстояние <= 1/M. Предположим, что такой точки не существует, тогда в одной из полосок у нас окажется как минимум две точки.
MP>Перенесем начало исходного луча в ближайшую из этих точек. Очевидно, что от этого переноса ничего не изменится,
А вот это надо бы доказать, как показано в примере с сеткой из получисленных точек перенос имеет значение
На самом деле вторая часть моего
доказательства является доказательством именно этого факта
MP>но вторая точка будет отстоять от луча на расстоянии <= 1/M. Таким образом мы доказали, что для любого целого M найдется целочисленная точка, отстоящая от луча на растояние <= 1/M. Осталось выбрать M > 1/r и утверждение доказано.
MP>P.S. Имхо, вполне по силам средним школьникам.
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, Apapa, Вы писали:
M>...
A>>Тогда так (чуть-чуть посложнее).
M>Для средних школьников?
A>>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
M>Поскольку (по первой задаче) луч проходит мимо некой точки с рациональными координатами M>(x = a/b, y = c/d) на расстоянии не более r` = r/bd, то (промасштабировав картинку на bd) он пройдёт мимо точки с целыми координатами (x = ad, y = cb) на (заданном) расстоянии r (r` * bd).
Данное решение неверно , попытаюсь это показать:
Для того, чтобы найти точку, от которой луч проходит на расстоянии меньшем r' надо зафиксировать b и d, но тогда не факт что будут существовать a и c удовлетворяющие условию. (Выберем b = 1 d = 1 — вот тебе исходная задача, основываясь на истинности которой ты ее же и доказываешь)
Здравствуйте, nikholas, Вы писали:
MP>Перенесем начало исходного луча в ближайшую из этих точек. Очевидно, что от этого переноса ничего не изменится,
N>А вот это надо бы доказать, как показано в примере с сеткой из получисленных точек перенос имеет значение N>На самом деле вторая часть моего
доказательства является доказательством именно этого факта
А с получисленными точками и решения нет! А с целочисленными точками сдвиг луча эквивалентен смещению целочисленной сетки без изменения положения луча, а т.к. сдвиги целочисленны, то картинка не меняется.
Я как раз этим пунктом своего доказательства больше всего горжусь! Этим, имхо, красивым приемом я обошел самую нудную часть доказательства. Хотя, если вдуматься, этот сдвиг практичеки точно соответсвует переходу к Z(i) в Вашем доказательстве.
Привет, MichaelP!
MP>Я как раз этим пунктом своего доказательства больше всего горжусь! Этим, имхо, красивым приемом я обошел самую нудную часть доказательства. Хотя, если вдуматься, этот сдвиг практичеки точно соответсвует переходу к Z(i) в Вашем доказательстве.
Гордись, гордись! Есть чем гордится!
Свое восхищение я уже высказал ранее
Здравствуйте, nikholas, Вы писали:
N>Данное решение неверно , попытаюсь это показать: N>Для того, чтобы найти точку, от которой луч проходит на расстоянии меньшем r' надо зафиксировать b и d, но тогда не факт что будут существовать a и c удовлетворяющие условию. (Выберем b = 1 d = 1 — вот тебе исходная задача, основываясь на истинности которой ты ее же и доказываешь)
Здравствуйте, mrhru, Вы писали:
N>>Данное решение неверно , попытаюсь это показать:
...
M> Ну конечно же. Неправильно!
В качестве извинений за своё упрямство ,
вот такая программа
double k = Math.PI;
double r = 0.00000001;
double y = 0.0, x = 1.0;
double dr = y - k * x;
// так неправильно:
// double dr = y/x - k;
// это как раз моя ошибка, на которой я упорствовалwhile ( Math.Abs(dr) > r )
{
if ( dr < 0.0 )
{
y++;
}
else
{
x++;
}
dr = y - k * x;
}
Console.WriteLine("{0}\t{1}\t{2}", y, x, dr);
позволяет обнаружить первую целую точку, и довольно быстро сходится.
PS. Вторая задача всегда имеет ещё одно решение, про которое не было ничего сказано.
Это точка (0, 0).
A>На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Если добавить "столбики ... и некоторой маленькой высотой h", то и любой пространственный луч, сонаправленный с осью Z и с ней не совпадающий.
A>Вот, вспомнилось...
A>На плоскости в точках с рациональными координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Ну да Вся плоскость будет забита этими столбиками без единого пятнышка Для любого действительного числа я легко найду рациональное, отклоняющееся не более, чем на h/2. Применяем эту операцию к любой паре чисел x, y, находим рациональную точку, под столбик которой попадает (x, y)
A>Тогда так (чуть-чуть посложнее).
A>На плоскости в точках с целыми координатами (кроме начала координат) стоят столбики некоторого маленького радиуса r. Доказать, что любой луч с началом в точке (0; 0) пересечет хотя бы один столбик.
Тоже тривиально.
Уравнение прямой: y = kx
Расстояние от точки (n, m) до этой прямой вычисляется по нехитрой формуле: d=|m-k*n|/sqrt(1+k*k). Нужно показать, что для любого действительного k, существуют n и m такие, что |m-kn|<r*sqrt(1+k*k)
Это равносильно тому, что для любого e, в последовательности {nk} существует число ближе к целому, чем e.
Докажем это по-простому. Одним из первых результатов в теории непрерывных дробей является тот факт, что для любого действитьльного a и целого числа y, существует дробь m/n, такая что |a — m/n| < 1/(y*y) и n < y (причем для ее находжнения есть детерминированный алгоритм). Это действительно простой результат. Все. Умножив неравенство на n, получим |a*n-m|<1/y. Берем любое целое y > 1/r*sqrt(1+k*k). Может найти m/n. Задача решена.
Apapa.gif)
Перекуём баги на фичи!
)
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Тоже хорошее доказательство!
, попытаюсь это показать:
Вся плоскость будет забита этими столбиками без единого пятнышка 