第319問の解答


問題 [場合の数]

問題図 左図のような一辺の長さが3cm立方体があり、各面が一辺1cm正方形マス目で区切られています。

このとき、図中のの位置からの位置まで、立方体辺上および各面のマス目上を通って最短距離(9cmですね)進む方法(図中にはその一例が赤線で示されています)何通りあるでしょうか。


解答例1

おかひで博士さん、ICさん、tropicanaさん、takuさん、 あんみつさん、 他

まず、平面の場合で考えます。

参考図1

 

上図のように縦m×横nマス目からなる格子線上対角線を結ぶ最短距離は、
 上へ進む場合をN右へ進む場合をE
で表すと、m個のNn個のE並べる方法の数に帰着されます。

従って、この場合は、(m+n)!/m!n!で求まります。

本問の場合、立方体は通れませんので上記式をそのまま拡張することはできません。

参考図1−2

そこで、上記図1のように各面に名前をつけます。

そして、図2のように展開図で考えると、からへ至る最短経路は、
2面分(縦3×横6)の最短経路と考えられます。

2面の組み合わせは、 ca、cd、ba、be、fd、fe の6通りあります。

それぞれの最短経路数=(3+6)!/3!6!=84通りなので、
 合計84×6=504通りとなります。

ただし、上記の数え方には、辺を共通にする組み合わせが6通り存在します。
cacdbabebefefdfebacacdfd

この場合の経路数は、それぞれ1面+1辺なので、(3+3)!/3!3!×6=20×6=120通り

従って、求める経路数は、504−120=384通りとなります。

答: 384通り

以上


解答例2

Miki Sugimotoさん、ヌオの母さん、ミミズクはくず耳さん、小西孝一さん、ほげさん、まるケンさん、M.Hossieさん、ただの酔っぱらいさん、ふじさきたつみさん、Taroさん、トトロ@Nさん、 他

格子状の各点を通る経路数について、次々と加算していって求めます。

参考図2

図3は、1面の場合です。

図4で各面について計算していくと、手前の点では、128通りとなります。

へは、3方向から合流するので、合計128×3=384通りと求まります。
 


解答例3

有無相生さん、ねこやんさん、 他

完全通る個数によって場合分けします。

参考図3

  • 3辺を通る場合:

を通る辺は3本、それぞれにつき面の2辺を通る方法は2通り
よって、3×2=6通り
(または、3方向に進む順番を決める方法=3!=6通り)

  • 1辺のみを通る場合

の数=を通るものが3本を通るものが3本=計6本
それぞれ、3×3のマス目の最短経路20通り−2辺を通る2通り=18通り

従って、合計=18×6=108通り

  • 1辺も通らない場合

通る面の組み合わせは6通り
2面を通り、辺を完全に通らないようにするには、上図のように2ケースに分けて考えると、
 9×3+3×6=45通り

従って、合計=45×6=270通り

従って、求める経路数=6+108+270=384通りとなります。


解答例4

中村明海さん、 他

SG中間地点を含む区間で区切って考えます。

参考図4

上図では、から4区間で到達する、Gから4区間で到達するを結ぶ線上を通る場合の数を、
それぞれ計算しています。

例えば、
 からへは2×2最短経路=(2+2)!/2!2!=6通り
 からへは1×3最短経路=(1+3)!/1!3!=4通り
従って、PQを通るのは、6×4=24通りという具合です。

隠れている面についても対象性を考慮して求めると、
 合計16×6+(24+24)×6=384通りになります。


解答例5

長野 美光さん、 他

から赤線中間線まで と、赤線からまでを考えます。

参考図5

図5では、から赤線の各点に始めて達するまでの経路数
図6では、赤線の各点からからまでの経路数を求めています。

従って、求める経路数の合計は、これらの掛け算を加えて、
 (4×6+10×3+20×1+10×3+4×6)×3=384通りとなります。