2020-共同作業-解説
- 考案国:ニュージーランド
- 正解
- 5
- 説明
- 作っている部品は7個あります。トレイをどのような順に回しても、集められない部品が2個できてしまいます。
- たとえば12番の部品を集めるためには、12分に12番の部品を集める必要があり、15分に3番の部品を集めて16分にxに渡すことになります。すると、15番は通れませんし、8分に8番の部品を集めてから12番に送ると13分になってしまいますので、8番と12番の両方を集めることはできません。
- 図を描きながら考えてみるとわかりやすいかもしれません。
- 実際のコンピュータでは
- この問題では、机を点に、机の間の縦横の移動を線にした「グラフ構造」で表すと考えやすくなります。問題の基本的な考え方は、スタートから始めて何個目の机かを数えながらトレイを渡していきますが、部品を作っている机には、できるだけ部品を作り終えた時間より後にトレイが回ってくる必要があります。
- このような、複数の条件が同時に満たされる問題を解くことは簡単ではありません。コンピュータも、どの机から始めてどの机の順序でトレイを回せばよいかを何度も試す必要がありますが、人間よりも処理が早いため、何百通りもの試行錯誤を行うことができます。