最短距離の問題です

質問

最短距離の問題です
座標空間において，x, y, z 座標の少なくとも1つが整数であるような点の集合 A を考える．
(0,0,0) から (3,3,3) まで，A に属する点だけを通って移動する
最短経路の長さを求めよ．

答えは√41 です

回答No.1

nag0720 · ベストアンサー

示された問題は、
1×1×1の立方体を27個、3×3×3の形に積み上げて、１つ頂点から反対側の頂点まで、立方体の面上を通って移動するときの最短経路と同じです。

縦横高さはそれぞれ３、合計９なので、最短経路を通る面を平面上に展開したときの縦横の長さの合計は最短でも９になります。

合計が９となる縦横の組(x,y)は、(1,8),(2,7),(3,6),(4,5)がありますが、
そのときの最短距離は、√(x^2+y^2)です。

上記の組で最短になるのは、(4,5)の場合で、
√(4^2+5^2)=√41

お礼

ありがとうございました