Räuber und Gendarm Menge N x N

Question

1. Ein Räuber R hat sich auf einem Punkt (x, y) ∈ N × N versteckt. Der Gendarm versucht den Räuber zu fangen indem er bei jedem Einsatz in einem Punkt in der Menge N × N nach dem Räuber sucht.
Kann der Gendarm seine Einsätze so planen, dass er den Räuber auf jeden Fall fängt? (Ein solcher Einsatzplan kann als eine Abbildung g : N → N × N aufgefasst werden.)
2. (*) Ein anderer Räuber S befindet sich an einem Startpunkt (a, b) ∈ N × N. Jedesmal nachdem der Polizist einen Einsatz fährt, bewegt er sich in eine ganz am Anfang fest gewählte Fluchtrichtung (v, w) ∈ N × N. Zunächst befindet sich der Räuber im Punkt (a, b), dann im Punkt (a+v,b+w), dann im Punkt (a+2v,b+2w) und so weiter.
Kann der Gendarm seine Einsätze so planen, dass er den Räuber auf jeden Fall fängt?

Problem/Ansatz:

Answer 1

1. Mathematisch formuliert lautet die Frage, ob es eine surjektive Abbildung von N nach N×N gibt. Die Antwort darauf liefert Cantors erstes Diagonalargument.

2. Das kann als Abbildung von N nach N × N × N × N aufgefasst werden. Auch hier liefert Cantors erstes Diagonalargument die Antwort darauf, ob es eine surjektive Abbildung gibt.