方針
セットAを セット、セットBを セットとおく。(1) は を3で割った余りを調べるだけである。(2) は余りなしなので を解き、(1)の合同条件と から候補を列挙する。(3) は のもとで費用 を最小化する。固定した に対して必要最小の を取り、 を3で割った余りで分類すると、調べる範囲を短くできる。
解答
(1)
3を法として考えると である。したがって が整数であることは、 が3で割り切れること、すなわち と同値である。よって のときに限り整数であり、それ以外の場合は整数ではない。
(2)
セットAを セット、セットBを セット購入するとする。購入した乗車券を余らせず100人で使うので である。ここで は0以上の整数である。
この式から である。(1)より、 が整数になるには が必要十分である。また だから である。
したがって の範囲で をみたすものは である。それぞれに対応する は である。よって購入の仕方は である。
(3)
今度は乗車券が余ってもよいので、条件は である。固定した に対して、費用を最小にするには、この不等式をみたす最小の を選べばよい。
まず なら、Aだけの費用ですでに である。一方、後で得る 円の購入方法があるので、最小を探すには だけを調べれば十分である。
のとき、必要なBの最小セット数は であり、費用は である。この場合 だから、最小は 、すなわち のとき である。
のとき、必要なBの最小セット数は であり、費用は である。この場合も だから、最小は 、すなわち のとき である。
のとき、必要なBの最小セット数は であり、費用は である。 なので、最小は 、すなわち のとき である。
以上を比較すると、購入金額が最も低くなるのは 購入するときであり、その金額は である。
総評
一次不定方程式と費用最小化を、合同条件で整理する問題である。目安時間は18分。(2) では余らせないため等式 、(3) では余ってもよいため不等式 と、条件が変わる点を明確に分けたい。(3) は全探索でも解けるが、 を3で割った余りで分けると、必要な と費用が一次式になり、境界の まで漏れなく処理できる。