Задачи по геометрии

chameleon54

Дано n точек,каждые три из которых не находятся на одной прямой,все они соединены отрезками либо красного,либо черного цвета.Найти наименьшее n,при котором существует 2 треугольника одного цвета.
2.a>b-целые числа.Оценить сверху количество шагов в алгоритме Евклида в зависимости от a.

afony

Вопрос по формулировке первой задачи: как понимать "2 треугольника одного цвета"? 1 треугольник с 3 красными сторонами и 1 треугольник с 3 черными подходят? Или нужно существование 2-х треугольников у каждого из которых по 3 красных или по 3 черных одновременно?

chameleon54

Как это по три красных и три черных одновременно?
Подходит 1 черный,1 красный

afony

Тогда ответ на первую задачу или 6 или 7. Сейчас соображу, хватит ли 6.
Во второй задаче, если я не ошибаюсь, точная оценка - само число a. Для a=2 имеем два шага:
2;1 -> 1;1 -> 1;0. А дальше по индукции: после первого шага a;b -> a-b;b, но для пары a-b;b по предположению индукции осталось не больше max{a-b,b}<a шагов. ЧТД.
P.S. В последнем вопросе имелось в виду что оба треугольника должны иметь не только три стороны одного цвета каждый, но эти цвета еще должны совпадать.

z731a

6

afony

Ну вот и хорошо, не надо на ночь голову ломать над вопросом 6 или 7.

chameleon54

спасибо большое

chameleon54

попросили доказать,что во второй задаче оценивается 2ln a сверху
так что опять актуально

Diossa

ээ почему 6?
там написано 2 трегольника а не 1

Diossa

ответ 7

chameleon54

препод подтвердил

afony

Тогда это не совсем тот алгоритм о котором я писал. Т.е. вместо перехода (a;b) -> (a-b;b) за один шаг идет переход (a;b)->(b; a mod (b) ).
Посмотрим что произойдет за 2 шага алгоритма. Положим c=a mod (b тогда c <= min{b-1,b-a} <a/2. Тогда два шага алгоритма (a;b) -> (b; c) -> (c; b mod (c. Т.е. за два шага алгоритма максимальное из двух чисел пары сократилось по крайней мере в 2 раза.
Теперь по индукции: для a=2 и a=3 оценка 2 log a (логарифм двоичный) очевидна.
При больших a, рассуждая как выше, получаем, что макс.число шагов алгоритма для a не больше 2+макс.число шагов алгоритма для a/2, что в свою очередь по предположению индукции не больше 2 + 2 log(a/2) = 2 log a.

z731a

>6
препод нагнал

ответ 6, если в условии говорится об одном одноцветном треугольнике

chameleon54

да,так и должно получиться

chameleon54

честно говоря,особо не вникала во все эти задачи по той простой причине,что целиком и полностью занята дипломкой
написала на случай,если у кого-нить больше свободного времени и есть желание порешать
оч клево,что такие нашлись!

kachokslava

Объясните, почему n=4 не подходит?

Или на самом деле задачу надо сформулировать так:
найти наименьшее n, такое что при любой раскрасске всегда получается 2 одноцветных треугольника?

neemah86

Ты ребра не все провел!
Легко доказывается, что для 6 всегда найдутся 2 треугольника.

alisa2009

ответ: 6 ...однозначно!

_mrz

Или на самом деле задачу надо сформулировать так:
найти наименьшее n, такое что при любой раскрасске всегда получается 2 одноцветных треугольника?
бугага и ты не угадал
вообще-то:
найти наименьшее n, такое что при любой раскраске всегда получается не меньше двух одноцветных треугольников?
А насчет первоначальной формулировки - "+1", конечно же ответ 4.
Оставить комментарий
Имя или ник:
Комментарий: