|
|
Автор: Большой Грызь
Дата : 03-02-05, Чтв, 16:33:18
|
Есть квадратное поле со стороной 1 км.
Известно, что под землей закопана бесконечно длинная прямая труба, но неизвестно, проходит ли она под этим полем или нет. Толщину трубы считать нулевой, т.е. труба представляет из себя бесконечно тонкую прямую линию, которая может проходить через квадрат, а может и проходить мимо.
В наличии имеется неограниченное кол-во миноискателей - эдаких палок, длиной один метр, которые кладут на землю и которые пищат, если под ними проходит труба. Т.е. миноискатель запищит даже, если под одной его точкой находится труба.
Какое минимальное кол-во миноискателей необходимо и как их следует расположить, чтобы со 100%-ной уверенностью сказать проходит ли труба под полем или нет.
Просто примеру ради - если мы расположим миноискатели по всему периметру, то мы со 100%-ной уверенностью сможем определить требуемое. И потребуется для этого 4км миноискателей (4000 штук). Но это далеко не самое оптимальное решение  А оптимальное - ищите |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Лапка с мелом
Дата : 03-02-05, Чтв, 23:33:38
|
Первый вариант: 2830 штук - по диагоналям квадрата. Кто меньше?
Оп! Уже нашла лучше! Сейчас обмозгую! |
[ 04-02-05, Fri, 6:40:20 Отредактировано: Лапка с мелом ] |
|
|
|
|
Автор: Лапка с мелом
Дата : 04-02-05, Птн, 00:18:44
|
Ага! Получается 2733 миноискателя!
Верно? |
[ 04-02-05, Fri, 7:19:55 Отредактировано: Лапка с мелом ] |
|
|
|
|
Автор: Эльдар
Дата : 04-02-05, Птн, 03:35:31
|
2708 |
|
|
|
|
Автор: Большой Грызь
Дата : 04-02-05, Птн, 06:19:15
|
Слушайте, давайте лучше не числами, а формулой. Считайте, что мниоискатели можно гнуть, как угодно. Мне нужна общая длина (даже необязательно целая) и форма той линии, по которой вы будете их раскладывать.
Т.е. задача сводится к тому, как провести линии миноискателей так, чтобы 100% пересечь любую прямую, проходящую через поле |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Паша
Дата : 04-02-05, Птн, 06:52:16
|
Мда, первое что приходит в голову это 2 + 1/2^0.5 Это как Эльдар посчитал.
Но минимум ли это? |
[ 04-02-05, Fri, 13:53:14 Отредактировано: Паша ] |
|
|
|
|
Автор: Лапка с мелом
Дата : 04-02-05, Птн, 07:05:58
|
Чтобы предусмотреть вариант, когда труба проходит только через одну точку - вершину квадрата, нужно начинать обязательно с углов. Это раз. Можно просто провести прямые отрезки до их пересечения в центре (т.е. диагонали) - соответственно общая длина миноискателей составляет две длины диагоналей - это 2828,5 метров. Отрезки, исходящие из вершин, должны обязательно пересекаться, чтобы "ловить" любую прямую, проходящую через поле. Это два. Есть вариант расположения миноискателей, предложенный на картинке:
Задача состоит в выборе такого значения X, чтобы длина всей конструкции (без учета сторон самого квадрата, конечно) была наименьшей. Обычная задачка на минимум функции одной переменной дает значение (предупреждаю, не целое) X = 422,6 м; а длину конструкции около 2732,05 метра. За счет целых длин миноискателей, предложенных вначале, можно было получить 2733 метра. Увы, у меня меньше не получается.
|
|
|
|
|
Автор: Лапка с мелом
Дата : 04-02-05, Птн, 07:07:06
|
Позвольте узнать, а как Эльдар рисовал себе это? |
|
|
|
|
Автор: Большой Грызь
Дата : 04-02-05, Птн, 08:57:52
|
Лапка, он нарисовал это так: + две стороны, у которых есть общая вершина (т.е. охвачены 3 вершины) + половина диагонали, исходящей из четвертой вершины. |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Лапка с мелом
Дата : 04-02-05, Птн, 09:12:26
|
Сдаюсь на милость победителям!
Это несомненно минимум в данной задаче! |
|
|
|
|
Автор: Паша
Дата : 04-02-05, Птн, 15:35:49
|
Какие вы все быстрые. Вопрос то остался. Как доказать, что это построение даёт минимальный результат. Кроме фраз, что меньше ещё никто не придумал... |
|
|
|
|
Автор: Большой Грызь
Дата : 04-02-05, Птн, 16:18:43
|
Угу
Докажите  |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Большой Грызь
Дата : 06-02-05, Вск, 03:33:33
|
На самом деле это не минимальное решение
|
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Эльдар
Дата : 07-02-05, Пнд, 01:07:27
|
Нашел еще меньше:
как доказать, что это наименьший вариант, пока не знаю. |
|
|
|
|
Автор: Паша
Дата : 07-02-05, Пнд, 16:47:15
|
Сразу видно, что есть ещё меньший вариант, сейчас посчитаю, но доказать его минимальность тоже не могу. |
|
|
|
|
Автор: Паша
Дата : 07-02-05, Пнд, 17:00:40
|
В общем такая вот формула (в км):
1.5^0.5 + 2^0.5
Это примерно равно 2639
Кто меньше? |
|
|
|
|
Автор: Большой Грызь
Дата : 07-02-05, Пнд, 17:03:28
|
Давайте с рисунками Или хотя бы описанием
Во задачка, а?  Кто ж найдет математическое док-во. |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Паша
Дата : 07-02-05, Пнд, 17:13:43
|
Грызь, а ты сам найди  |
|
|
|
|
Автор: Большой Грызь
Дата : 07-02-05, Пнд, 17:40:42
|
Паша, если ты имеешь в виду найти твой "рисунок" исходя из формулы, то не в такое время разве что с утра на свежую голову |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Паша
Дата : 07-02-05, Пнд, 17:56:47
|
Да ладно, посмотри на рисунок Эльдара. Очевидно, что если вместо окружности нарисовать два отрезка, то получится меньше. Теперь осталось только минимизировать по длине верхнего отрезка... |
|
|
|
|
Автор: Чук
Дата : 21-02-05, Пнд, 05:48:09
|
У меня получилось 2400 миноискателей. |
|
|
|
|
Автор: Чук
Дата : 21-02-05, Пнд, 05:53:31
|
О у меня получилось 2300 миноискателей |
[ 21-02-05, Пнд, 12:56:54 Отредактировано: Чук ] |
|
|
|
|
Автор: Большой Грызь
Дата : 21-02-05, Пнд, 05:56:45
|
Гм.. 1800?? Как |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Чук
Дата : 21-02-05, Пнд, 05:58:46
|
Автор: Большой Грызь
Дата : 21-02-05, Пнд, 12:56:45
Гм.. 1800?? Как
Я пошутил. 2300 получилось точно. Но это как у Эльдара. |
|
|
|
|
Автор: Большой Грызь
Дата : 21-02-05, Пнд, 06:05:57
|
Вообще-то у Эльдара вышло чуть больше, чем у Паши, а Пашин вариант - 2639.
А 2300 как? |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
|
|
Автор: Чук
Дата : 21-02-05, Пнд, 06:16:03
|
Автор: Большой Грызь
Дата : 21-02-05, Пнд, 13:05:57
Вообще-то у Эльдара вышло чуть больше, чем у Паши, а Пашин вариант - 2639.
А 2300 как?
Ну как бы 500м по нижнему левому краю наверх , потом наискось 500 к верхнему краю, и 500 по направо по верхнему краю и обособленная диния 500м наискось с правого нижнего угла к центру. А также линия пересекающая левый верхний край 300 м от центра той линии которая наискось.
Если конечно понятно высказался, я геометрию не помню и слов соответствуюших не знаю, я так логически. |
|
|
|
|
Автор: Чук
Дата : 21-02-05, Пнд, 06:20:50
|
Ой я неправильно посчитал там же диагональ больше стороны. Надо умножить, да всё правильно 2639. |
|
|
|
|
Автор: Большой Грызь
Дата : 21-02-05, Пнд, 06:22:25
|
Ага.. только вопрос остался открытым - минимум ли это? |
Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй) |
|
|
Новости
Чаты
88:88 
