Stellt euch vor, ihr besitzt 74088 exakt gleich große durchsichtige Plastikwürfel. Diese setzt ihr zu einem Quader der Seitenlängen 63*42*28 zusammen.
Jetzt schickt ihr einen Laserstrahl von einer Ecke des Quaders zur raumdiagonal gegenüberliegenden Ecke.
Wie viele Einzelwürfel berührt der Laserstrahl dabei?
PS: Wem das zu einfach ist, der darf den allgemeinen Fall eines Quaders mit den Seitenlangen A*B*C lösen.
Man schickt den Laserstrahl durch A hintereinanderliegende Würfel.
Trivial: Der Strahl durchquert A Würfel.
Man schickt den Strahl diagonal durch eine Fläche von A*B Würfeln.
\_ _ _ _ |_|_|_|_| |_|_|_|_| \
In x-Richtung werden jetzt immer noch genauso viele Würfel durchlaufen wie im eindimensionalen Fall; in y-Richtung auch. Probleme ergeben sich nur, wenn (wie oben in der Mitte des Rechtecks) Übergänge in einen neuen Würfel in x- und y-Richtung zusammenfallen. Da dies ggT(A,B) mal der Fall ist, durchläuft der Strahl A + B - ggT(A,B) einzelne Würfel.
Im dreidimensionalen Fall erhält man analog dazu
A + B + C - ggT(A,B) - ggT(A,C) - ggT(B,C) + ggT(A,B,C)
durchlaufene Würfel.
Für das angegebene Beispiel mit einem 63*42*28 Quader erhält man damit
63+42+28-21-7-14+7 = 98
durchlaufene Würfel.