Разбиение плоскости прямыми
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Разбиение плоскости прямыми - 2009-06-06 22:19:46.483333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Что-то я смотрю мода пошла толкать алгоритмические задачки. Я тут вспомнил одну. Пускай дано некое натуральное число N. Вопрос в том, можем ли мы проведя некое число прямых (попарно не параллельных) на плоскости разбить эту самую плоскость на N частей. Например, мы можем разбить на одну часть, если не будем проводить прямых вообще. Мы можем разбить на две части, если проведём одну прямую. Мы можем разбить на четыре части, если проведём две прямые. На три же части мы разбить не можем (если не будем делить двумя параллельными прямыми, что запрещено условием). Если подумать, можно сообразить что мы можем разбить на 2k частей, для любого натурального k: для этого надо просто провести k прямых проходящих через одну точку. Можно разбить на 3k+1 частей проведя (k-1) прямую через одну точку, а одну прямую так, чтобы она не содержала эту выбранную точку. Можно придумать ещё кучу таких чисел, на которые плоскость разбивается. Но хотелось бы уметь отвечать на поставленный вопрос для любого натурального N.
Эту задачу нам впихнул геометр на первом курсе. Я тогда пытался решить её аналитически (именно в таком контексте она и была преподнесена). То есть мне хотелось написать некую формулу которая выдавала бы при разных k все такие N для которых ответ в задаче положителен (ну или отрицателен). Дня через два марания бумаги у меня возникло чёткое ощущение, что решение этой задачи упирается в какую-то нерешаемую проблему… То ли мне понадобилась формула которая при разных k выдаёт все разные простые числа, то ли ещё что-то. Но это не важно, на данный момент я уже не студент-математик, и мне интереснее алгоритмическое решение. То есть алгоритм, который для любого N сможет сказать можно ли разбить плоскость на N частей каким-то числом прямых или нет.
|
|
|
|
|
RE: Разбиение плоскости прямыми - 2009-06-07 01:14:18.080000
|
|
|
FriLL
Сообщений: 2539
Оценки: 335
Присоединился: 2007-08-11 17:14:26.703333
|
может я чтото не понял но разве N/2 это не будет ответом?
Ведь количесто N не может быть нечетным, а если так оказалось то разбить плоскость нельзя
UPD
плокость с 3 прямыми можно разбить и на 6 или 7 частей - смотря как будут проходить прямые
|
|
|
|
|
RE: Разбиение плоскости прямыми - 2009-06-09 11:11:30.360000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
может я чтото не понял но разве N/2 это не будет ответом?
Нет, ответом будет либо "да", либо "нет", то есть логическая величина, но не число ;)
Задача вкратце. Надо ответить на вопрос, можно ли разбить плоскость на N частей (пускай число вводится с клавиатуры;)) проведя некое число прямых. Ответ либо "да", либо "нет". Конечно было бы неплохо знать то количество прямых которыми надо разбивать, но это уже необязательно.
В этой задаче самым замечательным является то, что судя по всему, для любого N, можно найти M (которое >N) для которого ответ в задаче будет отрицательным. Сильно неочевидный факт. И даже более того, на первый взгляд кажется что всё ровно наоборот: для мелких N ещё быть может не удастся разбить, а для больших, там где прямых много будет, по-любому можно как-то извернуться и разбить на такое число частей. Ан не тут-то было…
|
|
|
|
|
|
