Задача "Вася и тараканы"

[sergey zhukov]

Могу ответственно заявить: сколько бы тараканов на кухне вы ни поймали, их там меньше не станет. Всех переловить невозможно ни при каких условиях.

[sirvff]

Sender в сообщении #1645125 писал(а):

Ну почему же? Грубо говоря, если тараканы расползаются во все стороны от центра круга, при этом оставляя его внутренность более-менее равномерно заполненной, площадь разрастающегося заполненного тараканами круга будет расти квадратично со временем, а заметаемая Васей площадь -- линейно.

по вашему соображению не понятно, почему бы оно перестало работатить при $ r=0.99$, однако довольно-таки ясно, что при таком r кот всех переловит в ограниченном круге

ну пускай у нас в каждой точке тараканы, клякса такая растекается. из каждой точки вторично - как волнойвой фронт :)
во-первых квадратичный не квадратичный не знаю. кот же кушает.
второе, ну представьте ситуацию - Вася двигается прям очень быстро. Он выбегает на некий радиус и двигается кругами, и ни у одного таракана нет времени пересечь кольцо. То есть я просто хочу показать, что этих аргументов не достаточно. Может, есть граничное $r$ ?)

[mihaild]

sirvff в сообщении #1645173 писал(а):

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

Если тараканов бесконечно много, а кот точечный, то не получится. Если например тараканы распространяются из одной точки, то всё время будут закрывать собой круг максимум без одной точки, как бы кот не бегал.

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

[Geen]

mihaild в сообщении #1645177 писал(а):

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

С с учётом того, что скорость кота не более чем в два раза больше скорости тараканов, это разве не приводит к тому, что радиус кота больше 1 (в котором случае он их всех разом на старте хлопнет)?

[Sender]

sirvff в сообщении #1645173 писал(а):

То есть я просто хочу показать, что этих аргументов не достаточно. Может, есть граничное $r$ ?)

Ну понятное дело. Аргумент был против вашего утверждения, что при любом $r>0$ Вася побеждает.

sirvff в сообщении #1645173 писал(а):

ну пускай у нас в каждой точке тараканы, клякса такая растекается. из каждой точки вторично - как волнойвой фронт :)

Представим себе, что Вася движется по прямой, проедая тоннель шириной $2r$, при этом сразу за ним стенки тоннеля начинают сходиться. Очевидно, на расстоянии $2r$ от Васи стенки тоннеля сойдутся (при соотношении скоростей 2:1), т.е. за ним будет тянуться треугольник, свободный от тараканов. Площадь этого треугольника в первом приближении $2r^2$, т.е. большую площадь он не сможет зачистить. Если тараканы изначально занимают большую площадь, они победят.

-- Чт июл 04, 2024 22:09:21 --

mihaild в сообщении #1645177 писал(а):

сбегать внутрь за тараканом, вернуться и еще раз пробежать по окружности.

Кстати, непонятно, зачем бегать в центр. Можно же просто двигаться по архимедовой спирали к центру: если удалось описать окружность по большому радиусу, по меньшему это сделать ещё легче.

[mihaild]

Geen в сообщении #1645183 писал(а):

с учётом того, что скорость кота не более чем в два раза больше скорости тараканов

Это как раз про общее соображение о заметаемой площади.

[sirvff]

mihaild в сообщении #1645177 писал(а):

sirvff в сообщении #1645173 писал(а):

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

Если тараканов бесконечно много, а кот точечный, то не получится. Если например тараканы распространяются из одной точки, то всё время будут закрывать собой круг максимум без одной точки, как бы кот не бегал.

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

ну да
с точечным понятно всё.

-- 04.07.2024, 22:15 --

Sender в сообщении #1645184 писал(а):

sirvff в сообщении #1645173 писал(а):

То есть я
Представим себе, что Вася движется по прямой, проедая тоннель шириной $2r$, при этом сразу за ним стенки тоннеля начинают сходиться. Очевидно, на расстоянии $2r$ от Васи стенки тоннеля сойдутся (при соотношении скоростей 2:1), т.е. за ним будет тянуться треугольник, свободный от тараканов. Площадь этого треугольника в первом приближении $2r^2$, т.е. большую площадь он не сможет зачистить. Если тараканы изначально занимают большую площадь, они победят.

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

[Sender]

sirvff в сообщении #1645187 писал(а):

тут между прочем может быть важно, конечно там тараканов или как.

Примем для простоты, что бесконечно.

sirvff в сообщении #1645187 писал(а):

во-первых, ну может он вернулся и подчистил часть этого треугольника

Тут такое дело: площадь области тараканов увеличивается пропорционально её периметру. Если изначально они занимают единичный круг(за вычетом Васи), в единицу времени площадь прирастает на $2\pi v$. Вася в единицу времени уменьшает эту площадь максимум на $4rv$ (и пока не вышел на границу круга, увеличивает периметр на $2v$ плюс увеличение в самом начале движения на $\pi r$).

[Geen]

Пусть тараканов бесконечно много и они "диффундируют" на пустое пространство с "линейной" скоростью 1. Пусть кот бегает по окружности радиуса $\rho$. Тогда он окружность пробегает за время $\pi\rho$. Если $2r>\pi\rho$, то тараканы не смогут "выползти наружу", а кот может постепенно уменьшать $\rho$...

[EUgeneUS]

Geen в сообщении #1645192 писал(а):

Пусть тараканов бесконечно много и они "диффундируют" на пустое пространство с "линейной" скоростью 1. Пусть кот бегает по окружности радиуса $\rho$. Тогда он окружность пробегает за время $\pi\rho$. Если $2r>\pi\rho$, то тараканы не смогут "выползти наружу", а кот может постепенно уменьшать $\rho$...

да ладно. Ползет таракан, пересекает окружность радиуса $\rho$, и думает, "а почему бы мне не подождать кота, который от меня где-то по диаметру в данный момент"

[sirvff]

Sender в сообщении #1645190 писал(а):

sirvff в сообщении #1645187 писал(а):

тут между прочем может быть важно, конечно там тараканов или как.

Примем для простоты, что бесконечно.

sirvff в сообщении #1645187 писал(а):

во-первых, ну может он вернулся и подчистил часть этого треугольника

Тут такое дело: площадь области тараканов увеличивается пропорционально её периметру. Если изначально они занимают единичный круг(за вычетом Васи), в единицу времени площадь прирастает на $2\pi v$. Вася в единицу времени уменьшает эту площадь максимум на $4rv$ (и пока не вышел на границу круга, увеличивает периметр на $2v$ плюс увеличение в самом начале движения на $\pi r$).

ну да да что-то в этом есть всём, тогда получается есть некоторый граничный радиус кота при данной скорости что ли?

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

а потом можно к другим метрическим пространствам)

ну и насчёт спиралей. Таракану-то по перпендикуляру ползти вроде не самое, там чутка вкось траектория от кота получше будет, но не важно.

[sirvff]

1. Очевидно, достаточно толстый кот может поймать всех тараканов просто сделав небольшую спираль вокруг старта.
2. Остальное почти всё не очевидно.

Подзадача. Есть толстый кот радиуса 1 и есть бесконечно диффундирующая область тараканов D, расположенная где угодно. Кот в старте.
Привести хотя бы одно множество D, для которого кот не может всех съесть.
Классифицировать области на возможные к поеданию и невозможные.

Возможны ли области, из которых можно ограничить распространение тараканов, но съесть всех за конечное время при этом нельзя?

А в старших размерностях?

Ещё формулировка:
дело на клетчатой плоскости. И кот и таракан это 1 клетка. Все соседи занятой тараканом клетки тоже на следюущий код становятся таракановыми. А кот может за ход сожрать несколько клеток (можно считать что в ряд, можно - что любых, у кота телепорт)

какие множества кот сможет убить?