|
gagalka
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 27.11.2003
|
|
Сообщений: 386
|
|
Из: москва
|
|
Рейтинг: 26
|
|
разделить плоскость m прямыми
27.10.2005 21:33
|
|
|
на сколько частей можно?
известная вроде задача, никто сходу не помнит?
|
|
|
siliconec
|
|
|
|
|
|
|
|
|
Рег.: 02.04.2005
|
|
Сообщений: 13258
|
|
|
|
Рейтинг: 8773
|
|
Re: разделить плоскость m прямыми
[re: gagalka]
27.10.2005 22:16
|
|
|
А разве есть ответ (в смысле, однозначная функция от m)?
|
|
|
ais
|
|
CMXCIX-CXI
|
|
|
|
|
|
|
Рег.: 18.11.2003
|
|
Сообщений: 15489
|
|
|
|
Рейтинг: 387
|
|
Re: разделить плоскость m прямыми
[re: siliconec]
27.10.2005 22:19
|
|
|
Наверное имеется в виду максимум.
|
|
|
janisha
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 28.02.2003
|
|
Сообщений: 20140
|
|
|
|
Рейтинг: 5344
|
|
Re: разделить плоскость m прямыми
[re: gagalka]
27.10.2005 22:21
|
|
|
если k прямых провели, то (k+1) прямая может добавить к этим частям не более (k+1) новой части
добавится ровно (k+1) если (k+1) прямая пересечет каждую из этих k прямых в точках, отличных от их точек пересечений.
|
|
|
yakha
|
|
Pooh-Bah
|
|
|
|
|
|
|
Рег.: 20.10.2004
|
|
Сообщений: 2198
|
|
|
|
Рейтинг: 3
|
|
Re: разделить плоскость m прямыми
[re: janisha]
27.10.2005 22:24
|
|
|
четвертая, вроде добавляет только 3
|
|
|
Rott
|
|
|
|
|
|
|
|
|
Рег.: 07.09.2005
|
|
Сообщений: 4403
|
|
|
|
Рейтинг: 2885
|
|
Re: разделить плоскость m прямыми
[re: yakha]
27.10.2005 22:25
|
|
|
нет, 4 - и все остальные - соответственно
|
|
|
janisha
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 28.02.2003
|
|
Сообщений: 20140
|
|
|
|
Рейтинг: 5344
|
|
Re: разделить плоскость m прямыми
[re: yakha]
27.10.2005 22:26
|
|
|
3 прямых 7 частей
4 прямых - 11
|
|
|
yakha
|
|
Pooh-Bah
|
|
|
|
|
|
|
Рег.: 20.10.2004
|
|
Сообщений: 2198
|
|
|
|
Рейтинг: 3
|
|
Re: разделить плоскость m прямыми
[re: Rott]
27.10.2005 22:27
|
|
|
да, действительно, не досчитала
|
|
|
Rott
|
|
|
|
|
|
|
|
|
Рег.: 07.09.2005
|
|
Сообщений: 4403
|
|
|
|
Рейтинг: 2885
|
|
Re: разделить плоскость m прямыми
[re: yakha]
27.10.2005 22:29
|
|
|
|
|
|
siliconec
|
|
|
|
|
|
|
|
|
Рег.: 02.04.2005
|
|
Сообщений: 13258
|
|
|
|
Рейтинг: 8773
|
|
Re: разделить плоскость m прямыми
[re: janisha]
27.10.2005 22:32
|
|
|
все правильно
Quote:
если k прямых провели, то (k+1) прямая может добавить к этим частям не более (k+1) новой части
добавится ровно (k+1) если (k+1) прямая пересечет каждую из этих k прямых в точках, отличных от их точек пересечений.
Соотв
P(n)=P(0)+\sum _{k=1}^{n}k=1+n(n+1)/2
|
|
|
gagalka
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 27.11.2003
|
|
Сообщений: 386
|
|
Из: москва
|
|
Рейтинг: 26
|
|
Re: разделить плоскость m прямыми
[re: siliconec]
27.10.2005 22:34
|
|
|
угу, уже посчитали, спасиб!
а все какие варианты? мин - n+1, понятно, а дальше?
|
|
|
gagalka
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 27.11.2003
|
|
Сообщений: 386
|
|
Из: москва
|
|
Рейтинг: 26
|
|
Re: разделить плоскость m прямыми
[re: siliconec]
27.10.2005 22:34
|
|
|
и как эту формулу доказать/вывести? только по индукции?
|
|
|
siliconec
|
|
|
|
|
|
|
|
|
Рег.: 02.04.2005
|
|
Сообщений: 13258
|
|
|
|
Рейтинг: 8773
|
|
Re: разделить плоскость m прямыми
[re: gagalka]
27.10.2005 22:42
|
|
|
в индукции, как и в любом дрк\угом виде доказательства, нет ничего плохого - все открытия в конечном счете делаются по инд. или от частного к частному.
Очевидно, что можно новые прямые строить так, чтобы число новых кусков было любым от мин. до максимума. Это следует из того, что можно добавлять нужную конфигурацию последней прямой ко всем конфигурациям (не обязательно, максимальным) из n-1 прямых. Т.е. опять же, по индукции
|
|
|
Rott
|
|
|
|
|
|
|
|
|
Рег.: 07.09.2005
|
|
Сообщений: 4403
|
|
|
|
Рейтинг: 2885
|
|
Re: разделить плоскость m прямыми
[re: siliconec]
27.10.2005 22:46
|
|
|
нет, не очевидно...
Например, с помощью трет линий можно нарезать на 4, 6, 7 кусков, но нельзя на 5. С помощью 4 - нельзя нарезать на 6 и 7...
|
|
|
siliconec
|
|
|
|
|
|
|
|
|
Рег.: 02.04.2005
|
|
Сообщений: 13258
|
|
|
|
Рейтинг: 8773
|
|
Re: разделить плоскость m прямыми
[re: Rott]
28.10.2005 00:29
|
|
|
Может быть (нет времени рисовать)
Но задача с самого начала формулировалась в неуточненном виде. Очевидно, есть "запрещенные зоны" - но формулу их концов все равно можно установить только индуктивно, что и желаю автору задачи
Есть СНГ, что от n+2 до 2n -1, т.е граница - все параллельные и одна распараллеленная прямые
|
|
Список
Плоский
Дерево
