4 ms·
In my point-set topology class we used the diagonal argument as the root of a proof for the following question: Suppose a submarine is moving in a straight lin
by daturkel 13y ago
In my point-set topology class we used the diagonal argument as the root of a proof for the following question:
Suppose a submarine is moving in a straight line at a constant speed in the plane such that at each hour the submarine is at a lattice point. Suppose at each hour you can explode one depth charge at a lattice point that will kill the submarine if it is there. You do not know where the submarine is nor do you know where or when it started. Prove that you can explode depth charges in such a way that you will be guaranteed to eventually kill the submarine.
If there's interest, I'll post my solution. My proof actually gives an overview of what order to bomb points in, but I have no idea what it would look like if you plotted out, say, the first 100 or 1000 points. I'd be curious to see someone implement it.
- nmrm 13y agoThere's interest. I've taken point-set topology, so hopefully I'll be able to follow the proof without too much trouble. If so, building a simulation shouldn't be too difficult.
- daturkel 13y agoSee my reply to rkaplan's comment here: https://news.ycombinator.com/item?id=7544735 https://news.ycombinator.com/item?id=7544735
- rkaplan 13y agoI'm interested. What's the solution?
- daturkel 13y agoHere's a link to the proof I typed up for my problem set: https://www.sharelatex.com/project/534230c0234f079f3ce526fa?r=035466af&rs=ps&rm=d https://www.sharelatex.com/project/534230c0234f079f3ce526fa?... Theorem 1.10 states "If S andT are countable sets, the set S ×T ={(s,t) : s∈S,t∈T} is countable." and is proven using a diagonal argument.
- nmrm 13y agoMakes perfect sense. I'll code something up next weekend.
- cousin_it 13y agoThe set of all possible submarine routes is countable (velocity vector + position at time 0). Let's assume we have an enumeration of that set. Now it's easy to bomb them all. At time 1 we bomb the point where submarine 1 is at time 1, at time 2 we bomb the point where submarine 2 is at time 2, and so on.
- daturkel 13y agoYep, this is how the proof works!
- Someone 13y agoHow does that use the diagonal argument? If the diagonal argument could be used it would be to prove that the number of submarine routes isn't countable. Edit: just looked at the SVG called "Diagonal Argument.svg". That's not what I know as the diagonal argument (https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument, http://mathworld.wolfram.com/CantorDiagonalMethod.html http://mathworld.wolfram.com/CantorDiagonalMethod.html)