Разбиение плоскости на части #445830

На какое максимальное число частей разбивают плоскость n линий: 1. простой случай: линии это прямые. 2. сложнее: линии это окружности.

N ^n-1

во первых задачи две, во вторых это неверно, если я конечно правильно понял, что ты написал

1. 2n 2. n-1

не попал

2. 1 окружность разбивает на 2 части

на первую Ni = N(i-1)+N

для N0=1

на вторую - вломдумать

а N чему равно?

желательно не рекурсивную формулу, тогда уж как-то так: N(n)=N(n-1)+n

сумма арифметической прогрессии подставить нужно.

N(i)=N(i-1)+i

угу, и еще прибавить 1, будем считать, что решили как насчет второго пункта?

ты бы ещё в пятницу полпятого такой вопрос задал

в пятницу не так, в понедельник не так, среди недели тоже... эх...

N(i)=N(i-1)+2*i на вторую так?

2^n

окружности. одна окружность - две части (внутри и снаружи) две окружности - 3 части (вне зависимости, ести ли пересечения) три окружности - без пересечения четыре части, с пересечением попарно 1 с 2 и 2 с 3 - 6 частей, 1 с 2, 2 с 3, 3 с 1 - 8 частей задача не уточнена

написано же, на какое _максимальное_ число частей можно разбить плоскость

"максимально" тоже получилось 1. N(i) = N(i-1)+i 2. N(i) = N(i-1)+2*i

наверное так точнее N(i)=N(i-1)+2*(i-1)

2. 1-2 2-4 3-8 4-14

ага

осталось сгенерировать доказательство

идем методом от противного, рисуй пересечение 10 окружностей :)

По индукции :))

по индукции это да, осталось доказать, что всегда можно построить n окружностей так, что любые 2 имеют 2 точки пересечения и никакие 3 не пересекаются в одной точке.

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

=>

хотя для n>5 проверять влом :)

если 3 пересекаются в одной точке, то эт будет не максимальное количество частей

Максимальное количество разбиений будет только при наличии общей точки. Дальше каждая окружность разбивает пересекающие плоскости на 2 части.

гениально! это решение никто и не спорит

+ А дальше применяем аксиому индукции, задаем значение N и т. д.

окружности. если не пересекаются: N+1 если попарное пересечение: P + (N+1) SUM(i*P) + (N+1) где i - кратность пересечения (сколько окружностей пресеклаются)    P - количество таких пересечений N - число окружностей SUM - это большая фигурная буква епсилон (кажись так называется) Вроде бы так.

В принципе можно подробное доказательство забабахать

по второму пункту геометрическая часть в , алгебраическая ранее

Ок, понял, спасибо :) А откуда ты берешь такие задачки (просто ради интереса)?

из интернета в основном