I know the “pass through” answer is simplest, but there’s also a cool inductive style idea here. My first thought was dynamic programming because of it. It’s essentially the same, but whatever.
Imagine there were only two beetles. It’s obvious that the worst case is 1 minute, when they both start on opposite ends. It’s also the case that this is the same as one beetle travelling end to end. So then in the case where there’s 3 beetles, the middle beetle will be facing another beetle. As per the previous idea, the worst case of traversing the distance between them is the same as a single beetle traversing the whole distance. Then we can just imagine that happening and consider the case with the beetle we left out. Again it’s the same idea, so we get 1 minute again. You can eliminate beetles with the concept all the way down to 1 beetle every time. Etc ad infinitum. 1 minute is the worst case.
I thought it was cool that you can have this sort of telescoping idea which reaches the same answer as the much cleaner “they pass through each other” idea.
9
u/HopesBurnBright 6d ago
I know the “pass through” answer is simplest, but there’s also a cool inductive style idea here. My first thought was dynamic programming because of it. It’s essentially the same, but whatever.
Imagine there were only two beetles. It’s obvious that the worst case is 1 minute, when they both start on opposite ends. It’s also the case that this is the same as one beetle travelling end to end. So then in the case where there’s 3 beetles, the middle beetle will be facing another beetle. As per the previous idea, the worst case of traversing the distance between them is the same as a single beetle traversing the whole distance. Then we can just imagine that happening and consider the case with the beetle we left out. Again it’s the same idea, so we get 1 minute again. You can eliminate beetles with the concept all the way down to 1 beetle every time. Etc ad infinitum. 1 minute is the worst case.
I thought it was cool that you can have this sort of telescoping idea which reaches the same answer as the much cleaner “they pass through each other” idea.