Evolton

九州大学 2012年度 前期日程 第2次学力試験文系数学 第3問

100人の団体がある区間を列車で移動する。
このとき,乗車券が7枚入った480円のセットAと,
乗車券が3枚入った220円のセットBを購入して,
利用することにした。
以下の問いに答えよ。

(1) xが0以上の整数であるとき,次のことを示せ。

13(1007x)は,
xを3で割ったときの余りが1の場合に整数であり,
それ以外の場合は整数ではない。

(2) 購入した乗車券は,余らせずすべて利用するものとする。
このとき,セットAとセットBの購入の仕方をすべて挙げよ。

(3) 購入した乗車券は余ってもよいものとする。
このとき,Aのみ,あるいはBのみを購入する場合も含めて,
購入金額が最も低くなるのは,
ABをそれぞれ何セットずつ購入するときか。
またそのときの購入金額はいくらか。

難易度3/ 10計算量3/ 10目安18

整数 合同式、数え上げ、範囲評価

方針

セットAを x セット、セットBを y セットとおく。(1) は 1007x を3で割った余りを調べるだけである。(2) は余りなしなので 7x+3y=100 を解き、(1)の合同条件と 0x14 から候補を列挙する。(3) は 7x+3y100 のもとで費用 480x+220y を最小化する。固定した x に対して必要最小の y を取り、x を3で割った余りで分類すると、調べる範囲を短くできる。

解答

(1)
3を法として考えると 1007x1x(mod3) である。したがって 1007x3 が整数であることは、1007x が3で割り切れること、すなわち 1x0(mod3) と同値である。よって x1(mod3) のときに限り整数であり、それ以外の場合は整数ではない。

(2)
セットAを x セット、セットBを y セット購入するとする。購入した乗車券を余らせず100人で使うので 7x+3y=100 である。ここで x,y は0以上の整数である。

この式から y=1007x3 である。(1)より、y が整数になるには x1(mod3) が必要十分である。また y0 だから 0x14 である。

したがって 0x14 の範囲で x1(mod3) をみたすものは x=1,4,7,10,13 である。それぞれに対応する yy=31,24,17,10,3 である。よって購入の仕方は (A,B)=(1,31),(4,24),(7,17),(10,10),(13,3) である。

(3)
今度は乗車券が余ってもよいので、条件は 7x+3y100 である。固定した x に対して、費用を最小にするには、この不等式をみたす最小の y を選べばよい。

まず x15 なら、Aだけの費用ですでに 480x48015=7200 である。一方、後で得る 6900 円の購入方法があるので、最小を探すには 0x14 だけを調べれば十分である。

x=3k のとき、必要なBの最小セット数は y=347k であり、費用は 480(3k)+220(347k)=7480100k である。この場合 k=0,1,2,3,4 だから、最小は k=4、すなわち x=12,y=6 のとき 7080 である。

x=3k+1 のとき、必要なBの最小セット数は y=317k であり、費用は 480(3k+1)+220(317k)=7300100k である。この場合も k=0,1,2,3,4 だから、最小は k=4、すなわち x=13,y=3 のとき 6900 である。

x=3k+2 のとき、必要なBの最小セット数は y=297k であり、費用は 480(3k+2)+220(297k)=7340100k である。k=0,1,2,3,4 なので、最小は k=4、すなわち x=14,y=1 のとき 6940 である。

以上を比較すると、購入金額が最も低くなるのは A13セット,B3セット 購入するときであり、その金額は 6900 である。

総評

一次不定方程式と費用最小化を、合同条件で整理する問題である。目安時間は18分。(2) では余らせないため等式 7x+3y=100、(3) では余ってもよいため不等式 7x+3y100 と、条件が変わる点を明確に分けたい。(3) は全探索でも解けるが、x を3で割った余りで分けると、必要な y と費用が一次式になり、境界の x=14 まで漏れなく処理できる。

冊子PDFで見る九大の整数の問題で問題集を作る

出典: 九州大学 2012年度 前期日程 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。