公務員試験 H29年 国家一般職(土木) No.8解説

　問 題　　　　　

図のような四角錐の頂点Aから出発し、四角錐の辺上を通って頂点を次々に移動する経路を考える。

ある頂点から辺で結ばれた隣の頂点のいずれかへの移動を1回の移動とし、1回の移動では最短経路をとるものとする。

このとき、頂点Aから4回の移動を終えた時点で頂点Aにいるような移動経路の数は全部でいくつか。

1．8

2．16

3．24

4．32

5．40

　解 説　　　　　

選択肢からせいぜい40通りなので、最悪数え上げようと考えます。AとA以外の４つの頂点に分けると考えやすいです。

１：A→A以外への移動

A→A以外は100%移動します。この移動は移動先が B,C,D,E なので４通り考えられます。

２：A以外→Aへの移動

これは 1 通りです。

３：A以外→A以外への移動

これは２通り考えられます。

【１回めの移動】

A→A以外なので４通り考えられます。

【２回めの移動（１）】

A以外→A と２回めに移動したとします。すると３回めの移動が A→A以外と確定します。

４回めにAにいるためには A以外→A→A以外→A　と移動しなければなりません。このパターンは１×４×１=４通りです。

１回めの移動が４通りあったので、このパターンは４×４=１６通りです。

【２回めの移動（２）】

A以外→A以外と２回めに移動したとします。すると、３回めの移動でAに行ってしまうと、どうしても４回めの移動でA以外に行ってしまいます。

従って、A以外→A以外→A以外→A　と移動しなければなりません。このパターンは２×２×１=４通りです。

１回めの移動が４通りあったので、このパターンは４×４=１６通りです。

以上より、合わせて３２通りが正解となります。

全てのパターンをあげてみると

1. A→B→A→B→A
2. A→B→A→C→A
3. A→B→A→D→A
4. A→B→A→E→A
5. A→C→A→B→A
6. A→C→A→C→A
7. A→C→A→D→A
8. A→C→A→E→A
9. A→D→A→B→A
10. A→D→A→C→A
11. A→D→A→D→A
12. A→D→A→E→A
13. A→E→A→B→A
14. A→E→A→C→A
15. A→E→A→D→A
16. A→E→A→E→A
17. A→B→C→B→A
18. A→B→C→D→A
19. A→B→E→B→A
20. A→B→E→D→A
21. A→C→B→C→A
22. A→C→B→D→A
23. A→C→D→C→A
24. A→C→D→E→A
25. A→D→C→B→A
26. A→D→C→D→A
27. A→D→E→B→A
28. A→D→E→D→A
29. A→E→B→C→A
30. A→E→B→E→A
31. A→E→D→E→A
32. A→E→D→C→A

です。