![]() |
![]() |
|
Информационные технологии
:: Математика и алгоритмы
|
|
| ||
НафНаф 23.01.13 - 10:29 | Можно ли на евклидовой плоскости отметить 4 точки так, что все попарные расстояния между ними были положительными целыми числами? а если добавить условие нечетности расстояний? | ||
1C-band 1 - 23.01.13 - 10:34 | Можно. Для начала - треугольник со сторонами 3 и 4. Длина гипотенузы будет равна 5. Дорисовываем четвёртую точку - вуаля!
ЗЫ: Что такое - нечётность расстояний? | ||
Wobland 2 - 23.01.13 - 10:35 | а что такое отрицательное расстояние? | ||
НафНаф 3 - 23.01.13 - 10:36 | |||
1C-band 4 - 23.01.13 - 10:38 | (3) В моём случае - нет, поскольку все остальные длины будут произведениями минимальных (3, 4 и 5 соответственно) на какое-либо число, и в результате расстояния будут как чётными, так и нет. Но это - только В МОЁМ случае, я имею ввиду прямоугольник с рёбрами длиной 3 и 4. | ||
НафНаф 5 - 23.01.13 - 10:40 | (4) в твоем все понятно, даже в произвольном прямоугольном, а не только твоем | ||
1C-band 6 - 23.01.13 - 10:41 | (5) Вот надо посмотреть, могут ли быть ещё варианты размещения точек, и какие. | ||
acsent 7 - 23.01.13 - 10:41 | задача сводится к нахождению пифагоровых чисел | ||
НафНаф 8 - 23.01.13 - 10:42 | (7) с чего это вдруг? | ||
acsent 9 - 23.01.13 - 10:42 | 6,8,10 - все четные | ||
НафНаф 10 - 23.01.13 - 10:42 | (9) к чему это? Рекламное место пустует | ||
1C-band 11 - 23.01.13 - 10:42 | (0) А ты там, случаем, не карты ли по полигонам раскраивать решил? | ||
acsent 12 - 23.01.13 - 10:42 | 4 вершины прямоугольника, все расстояния целые. Ну это подмножество решений как минимум | ||
НафНаф 13 - 23.01.13 - 10:42 | (11) зачем? | ||
1C-band 14 - 23.01.13 - 10:43 | (9) Речь шла о НЕЧЁТНОСТИ. | ||
acsent 15 - 23.01.13 - 10:43 | в пифагоровых тройках не могут | ||
НафНаф 16 - 23.01.13 - 10:43 | |||
KishMish 17 - 23.01.13 - 10:46 | (12) диагональные расстояния тоже целые? | ||
ptrtss 18 - 23.01.13 - 10:56 | (0) Можно. На прямой, через единицу | ||
НафНаф 19 - 23.01.13 - 11:03 | Итак решаем именно вторую часть задачи:
Можно ли на евклидовой плоскости отметить 4 точки так, что все попарные расстояния между ними были целыми нечетными числами? | ||
Lama12 20 - 23.01.13 - 11:04 | (18) Красава! | ||
Lama12 21 - 23.01.13 - 11:04 | (19) А вот это, нельзя. Т.к. любая пара даст четное расстояние. | ||
Lama12 22 - 23.01.13 - 11:05 | (21) Упс... не однозначно. | ||
НафНаф 23 - 23.01.13 - 11:05 | (21) чего? | ||
Лодырь 24 - 23.01.13 - 11:26 | Сделаем утверждение:
1. Если построение возможно, то построение возможно и при одной из точек (0,0) В таком случае можем принять одну из точек за Т1(0,0). Пусть координаты второй точки Т2 (Х2,У2) и третьей Т3(Х3,У3). Тогда квадрат длины отрезка (Т1,Т2) = Х2*Х2+У2*У2 - нечетное целое. Значит либо Х2 либо У2 - четное (тк иначе бы сумма квадратов была бы четной). Аналогично находим что либо Х3 либо У3 четное. Запишем квадрат длины отрезка (Т2,Т3) = (Х2-Х3)*(Х2-Х3)+ (У2-У3)*(У2-У3) - нечетное целое. Теперь разберем все варианты: 1. Х2 - чет, У2 - нечет, Х3- чет,У2-нечет. Получаем что четное*четное+четное*четное = нечетное. не бывает. 2. х2 чет, у2 нечет, х3 нечет У2 - чет. Получаем нечет*нечет+нечет*нечет = нечет. не бывает. 3. аналогично. 4. аналогично. Вывод - не бывает. | ||
НафНаф 25 - 23.01.13 - 11:30 | (24) ты только что доказал, что не существует равностороннего треугольника с длиной стороны 1.
Причина: неверное предположение, что либо Х2 либо У2 - четное На самом деле они вообще могут быть нецелыми | ||
Лодырь 26 - 23.01.13 - 11:40 | (25) Кхм.. логично. | ||
ptrtss 27 - 23.01.13 - 13:43 | А есть решение не полным перебором если? | ||
НафНаф 28 - 23.01.13 - 14:00 | (27) есть, а интересно как полным перебором? | ||
ptrtss 29 - 23.01.13 - 14:38 | (29) Шесть нечетных длин отрезков задаешь, и смотришь, какой получился седьмой. Если нечетный, значит решение найдено. Четный или дробный - следующая комбинация | ||
GrIM 30 - 23.01.13 - 14:44 | Вот ведь людям заняться нечем. Недавно видать закончили, фантомные боли... преследуют. | ||
acsent 31 - 23.01.13 - 14:52 | (24) неверно предположение, что концы треугольника должны лежать в целых точках | ||
Dmitry77 32 - 23.01.13 - 14:57 | можно на обной прямой разместить через 1 еденицу измерения расстояния будут
1,2,3,4 | ||
Lama12 33 - 23.01.13 - 15:11 | (32) Ну да... и между первой и третьей сумма сколько? | ||
RomanYS 34 - 23.01.13 - 19:01 | AB = 91
BC = 255 CA = 273 BD = 293 AD = 285 CD = 83 проверяй) | ||
НафНаф 35 - 25.01.13 - 11:27 | (34) не прокатило )) | ||
RomanYS 36 - 25.01.13 - 11:57 | (35) так и знал
есть более точные варианты )) Как проверял, есть какие-то формулы, или только построение и вычисление координат? | ||
SUA 37 - 25.01.13 - 12:18 | Невозможно, если в формулах не напутал нигде
долго крутить квадрат расстояний и факт что разница квадратов 2х нечетных чисел делится на 4 | ||
RomanYS 38 - 25.01.13 - 12:26 | (37) а ты точно не целочисленные координаты рассматривал?
у меня формулы дикие получаются, с корнями и 5-ю переменными, привести их разнице квадратов точно не получится. Возможно я не с той стороны захожу | ||
SUA 39 - 25.01.13 - 12:27 | с начальными D(0,0),A(a,0),B(b1,b2),C(c1,c2):
- все первые координаты рациональны (СD^2-СA^2=aa-2*c1a=N1, отсюда рациональна с1, аналогично b1) - b2-c2 рациональна | ||
SUA 40 - 25.01.13 - 12:28 | 5 переменных но уже 3 из них приводимы к целочисленным | ||
RomanYS 41 - 25.01.13 - 12:38 | Я брал 5 длин и находил по ним шестую. Первые 2 точки задавал также как у тебя. С тем что все x-координаты рациональны соглашусь. А вот в b2 и c2 у меня корни.
Откуда вывод "b2-c2 рациональна"? | ||
RomanYS 42 - 25.01.13 - 12:41 | |||
НафНаф 43 - 25.01.13 - 13:16 | Введем координаты так, что A(0,0) B(a,0) C(x,y) D(z,t)
Для вещественных p,q и целого положительного n введем обозначение p~q(mod n) того, что разность (p-q) целая и делится на n. Заметим тот факт, что квадрат нечетного числа дает остаток 1 при делении на 8. Или в обозначениях r~1(mod 2) => r^2 ~ 1(mod 8). Тогда: 1. x^2+y^2 ~ 1(mod 8) 2. (a-x)^2+y^2 ~ 1(mod 8) 3. z^2+t^2 ~ 1(mod 8) 4. (a-z)^2+t^2 ~ 1(mod 8) 5. (x-z)^2+(y-t)^2 ~ 1(mod 8) Из 1 и 2 отношения получаем: a^2 ~ 2*x*a (mod 8). Поэтому х - рациональное, его знаменатель является делителем 2*a и сам делится на 2. Аналогично из 3 и 4 отношения это верно и для z. Умножим все координаты всех точек на нечетное a. Все расстояния умножатся также на a, то есть если предположение верно для начальной конструкции, то оно верно и для промасштабированной. Переобозначим все новые координаты теми же буквами. Теперь мы можем утверждать, что x и z - рациональные числа со знаменателем 2. Вернемся к a^2 ~ (2*x)*a (mod 8), так как a - нечетное, то верно: a ~ (2*x) (mod 8), что эквивалентно a=2*x+8*n, где n - целое. Разделим на 2: a/2=x+4*n => x ~ a/2 (mod 4) x ~ a/2 (mod 4) => x^2 ~ a^2/4 (mod 4) => y^2 ~ 1 - a^2/4 (mod 4) аналогично верно: z ~ a/2 (mod 4), z^2 ~ a^2/4 (mod 4), t^2 ~ 1 - a^2/4 (mod 4) Вместе: x-z ~ 0 (mod 4) => (x-z)^2 ~ 0 (mod 8) и подставляем в отношение №5: (x-z)^2+(y-t)^2 (mod 8) => (y-t)^2 ~ 1(mod 8) => (y-t)^2 ~ 1(mod 4) Рассмотрим (y+t)^2 = 2*y^2+2*t^2- (y-t)^2 ~ 2 - a^2/2 + 2 - a^2/2 - 1 (mod 4) 2 - a^2/2 + 2 - a^2/2 - 1 = 3-a^2 ~ 2 (mod 4), коротко: (y+t)^2 ~ 2 (mod 4) Перемножим (y-t)^2 ~ 1(mod 4) и (y+t)^2 ~ 2(mod 4), получим: (y^2-t^2)^2 ~ 2(mod 4), но y^2 ~ t^2 (mod 4), то есть (y^2-t^2)^2 ~ 0 (mod 4) - противоречие | ||
SUA 44 - 25.01.13 - 13:22 | да, примерно... реально вычислений достаточно много | ||
RomanYS 45 - 25.01.13 - 13:25 | В https://ru.wikipedia.org/wiki/Четырёхугольник есть формула "Шесть расстояний между четырьмя произвольными точками плоскости, взятыми попарно, связаны соотношением", если взять его по модулю 4 для нечетных чисел получим слева 2, а справа 0 | ||
НафНаф 46 - 25.01.13 - 13:27 | (45) ага, кто бы про нее еще знал)) | ||
RomanYS 47 - 25.01.13 - 13:32 | (46) Я ее больше нигде не нашел, причем порядок (выбор a,b,c,d,e,f) в ней влияет на результат. А как правильно обозначить не указано )) | ||
НафНаф 48 - 25.01.13 - 13:51 | (47) исходя из симметрии достаточно чтобы пары (a,c), (b,d) и (e,f) не имели общих вершин, то есть либо были противоположными сторонами, либо диагоналями |
|
Список тем форума
|
Правила | Описание | Реклама на форуме | Волшебные решения | Поиск | Секции | Рейтинг | Книга знаний | Вики-миста (КЗ2) | Мобильная | Архив | Модераторы | Галерея | Регистрация | 18+ |