2017年度「アルゴリズムとデータ構造」のページ

練習問題

2017年11月30日出題
  1. [ポロック予想](2017年12月14日加筆) 正四面体数、立方数、正八面体数は、以下で計算できる。

    • \(n\)番目の正四面体数は \(n(n+1)(n+2)/6\) である。
    • \(n\)番目の立方数は \(n^3\) である。
    • \(n\)番目の正八面体数は \(n(2n^2+1)/3\) である。

    初めのほうの正四面体数、立方数、正八面体数を列挙すると、以下の通りである。

    • 正四面体数は \(1,4,10,20,\ldots\) である。
    • 立方数は \(1,8,27,64,\ldots\) である。
    • 正八面体数は \(1,6,19,44,\ldots\) である。

    1850年、職業数学者ではなく英国の法律家でありトーリー党(現在の保守党)の政治家でもあった初代准男爵フレデリック・ポロック卿が、次の三つを予想した。

    • すべての正整数は5個以内の正四面体数の和として表現できる。
    • すべての正整数は9個以内の立方数の和として表現できる。
    • すべての正整数は7個以内の正八面体数の和として表現できる。

    ただし、和の中で同じ数が複数回出現してよく、その場合、それぞれの出現を別々に数えるものとする.

    三つの予想のうち、立方数に関するものだけは20世紀初めに正しいことが証明された。残りの二つは、一世紀半以上も未解決なままである.

    1. 正整数を次々と入力し、それぞれについて以下の三つの数を計算して出力するプログラムを書け。

      • 入力した数を正四面体数の和として表すための正四面体数の個数の最小値
      • 入力した数を立方数の和として表すための立方数の個数の最小値
      • 入力した数を正八面体数の和として表すための正八面体数の個数の最小値

      例えば、\(8\)については \[ \begin{aligned} 8 &= 2\times3\times4/6 + 2\times3\times4/6 \\ 8 &= 2^3 \\ 8 &= 1\times(2\times1^2+1)/3 + 1\times(2\times1^2+1)/3 + 2\times(2\times2^2+1)/3 \end{aligned} \] と、二つの正四面体数の和、一つの立方数の和、三つの正八面体数の和で表すことができ、これが最小個数なので、8 が入力されたときは 2 1 3 と出力しなくてはならない。

      入力は、\(10^8\)よりも小さいと仮定してよい。

  2. [多面体上の経路] すべての面が合同な正多角形で、すべての頂点の近傍が合同な凸多面体を、正多面体という。正多面体はプラトンの立体とも呼ばれる。全部で5種類ある。

    正多面体(プラトンの立体)
    頂点 点対称?
    正三角形 正方形 正五角形
    正四面体 4 6 4 ×
    立方体(正六面体) 8 12 6
    正八面体 6 12 8
    正十二面体 20 30 12
    正二十面体 12 30 20

    すべての面が正多角形で、すべての頂点の近傍が合同な凸多面体のうち、正多面体と角柱と反角柱を除いたものを、半正多面体という。正多面体はアルキメデスの立体とも呼ばれる。全部で13種類ある。

    半正多面体(アルキメデスの立体)
    頂点 点対称?
    正三角形 正方形 正五角形 正六角形 正八角形 正十角形
    切頂四面体 12 18 4 4 ×
    切頂立方体(切頂六面体) 24 36 8 6
    切頂八面体 24 36 6 8
    立方八面体 12 24 8 6
    大斜方立方八面体(切頂立方八面体) 48 72 12 8 6
    斜方立方八面体 24 48 8 18
    捻れ立方体(変形立方体) 24 60 32 6 ×
    切頂十二面体 60 90 20 12
    切頂二十面体 60 90 12 20
    十二面二十面体 30 60 20 12
    斜方十二面二十面体 60 120 20 30 12
    大斜方十二面二十面体(切頂十二面二十面体) 120 180 30 20 12
    捻れ十二面体(変形十二面体) 60 150 80 12 ×
    1. 以下の多面体について、ある頂点から多面体の中心を対称の中心として点対称の位置にある頂点への多面体の辺に沿った経路で、同じ頂点を複数回通らないものを、数えるプログラムを書け。経路の長さ(経路に含まれる辺の本数)ごとの経路の個数と、経路の総数を出力せよ。

      多面体ごとに別々のプログラムを書いても、一つのプログラムで全部に対応しても、どちらでも良い。 入出力の形式は各自で決めて、取扱説明書に書くこと。 提出には取扱説明書も加えること。

      1. 立方体(正六面体)
      2. 正八面体
      3. 立方八面体
      4. 切頂立方体(切頂六面体)
      5. 切頂八面体
      6. 斜方立方八面体
      7. 大斜方立方八面体(切頂立方八面体)
      参考
      正多面体、準正多面体、ザルガラー多面体、mxico (Nakata Maho)
    2. (おまけ)以下を証明せよ。(文献を調べた場合は出典明記を忘れずに)

      1. 正多面体はちょうど5種類である。
      2. 半正多面体は(正多面体と正角柱と正反角柱を除いて)ちょうど13種類である。

戻る