На плоскости задали 12 точек, никакие 3 не лежат на одной прямой. Начали их соединять прямыми отрезками. Вопрос сколько максимально можно провести отрезков, чтобы никакие два из них не пересеклись?

11

(1) нет

начнём. количество отрезков менее 64?

(2)т.е. из одной точки можно проводить к нескольким точкам?

20

(4) да

(6) менее 32?
//шучу, думать тяжело уже

(7) не так прочитал (6)

3*12-6=30

21?

25

27

21

интересней доказать что больше 30 нельзя

12 + 6 + 3 = 21

22

я насчитал 19

(16)+ неа. все-таки(13) 21.

если в центр одну точку то 22

(15) откуда 12 речь о отрезках если точек 12 то отрезков -1 не так ли? +6-1 +3

(15)Я считала (н-1)+(н-2). А как рисуется по 6 и 3?

(20)
замкнуть.
многоугольник
?

(14) Все доказано до нас.
wiki:Планарный_граф

Зависит от того можно ли соединить точки так, что хотя бы одно попадет внутрь фигуры.

если точки в пространстве - 38 получится...

(19)Хм... А если 2?

(23) планарный не требует прямых линий, тут это обязательно

29

(22)Ну да

треугольник, в нем точка соединяется с 3 вершинами - далее рекурсия...
для пространства - тетраэдр

(21) Ну как бы сначала соединяем многоугольник
потом через одну точку еще 5 линий получаем
потом еще 3 можно отрисовать.

(30) речь о точках на плоскости вроде

3+(12-3)*3 = 30 для плоскости

да 30, только логика в (9) не понятна

(27) Рисуем большой треугольник. Остальные точки помещаем внутрь треугольника. Проводим отрезки, так чтобы большой треугольник был разбит на маленькие треугольники. Это всегда возможно. получим ровно 30 отрезков.

(30) а ведь ты прав!

если строить треугольники то формула вроде такая
(КвоТочек-3)*3+3

(34) Точки будем называть вершинами В. Отрезки ребрами Р. Каждую область ограниченную отрезками будем называть гранью Г. Также гранью будем называть область в которой помещаются все наши точки.

Формула Эйлера: В-Р+Г=2. Максимум ребер получим, когда все наши грани треугольники. Т.е. 3В=2Р.

Р=3В-6

(34) в (9) ответ из wiki:Планарный_граф
в планарном графе ребер <= 3*вершин - 6

(38) Ошибка вышла. Надо читать:
Максимум ребер получим, когда все наши грани треугольники. Т.е. 3Г=2Р.

66

(27) Любой планарный граф можно представить в виде грава с прмыми ребрами

31

(43) ответ уже давно дан. 30

21?

21

(44) нарисуй

Без всяких формул по наитию видно, начертив простой чертеж - 21.

Вроде 30.

Прямая цепочка из 10 вершин - 9 отрезков
две вершины с двух сторон от цепочки, соединенные с каждой
- 2*10 отрезков
эти две вершины между собой - 1 отрезок

Цепочку слегка изгибаем, чтобы не на одной прямой.

И вообще, для N>=3 вершин
3+(N-3)*3 ребер

Берем полный граф с тремя вершинами - (3 ребра)
Добавляем вершины по одной.
На любой итерации,
при добавлении новой вершины (куда бы мы её не добавляли),
мы можем провести от неё
максимум 3 прямых отрезка к другим вершинам.
И так далее по индукции.

(47) Зачем? И так же понятно.

1





  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

                                                  12

1 соединен со всеми - 11 отрезков.
12 соединен со всеми - 10 отрезков (1-12 считаем один раз)
2-3-4-5-6-7-8-9-10-11 - еще девять отрезков
вообще см (49)

(48) Слабое у тебя наитие.

1          12
     

     2
     3
     4
     5
     6
     7
     8
     9
     10
     11

вот так красивее.