2020年(令和2年)久留米大学附設中学校-算数[4]

数学 プログラム

f:id:spherical_harmonics:20200322060223j:plain

2020.03.22記
最近プログラムの講義をもっていないが、いつかやるときのためのネタとして覚え書き。中学入試の算数の問題はアルゴリズム的な問題が結構多いのだ。

それにしても、プログラムをさせておいて、その数学的背景を語る講義をやる機会って来るのかなぁ。

という訳で数学的背景は倍数判定法。
中学入試なので、問題文において整数といえば非負整数を指すことに注意しておく。

x の1の位を消してできる新たな非負整数から、消した 1 の位のk倍を引くという操作

y = ( x / 10 ) - k * ( x % 10 )

を繰り返して0になるかどうかを考える。0にならない場合は負になってしまうので、これを終了条件とすれば良い。

プログラムを作らせた後に、どんな入力なら0になるかを確認させるために、x を 0 から 1000 ぐらいまで for 文で回してやった後に解説。
すると、「10k+1の倍数のときに0となる」ことが予想できる。

x=10a + b のとき、f(x)=a-kb とすると、
f(x)=a-k(x-10a)=(10k+1)a-kx
が成立するので、倍数判定したいn に対して 10k+1 \equiv 0\,(\mod n) なる k を選ぶことができれば(10とnが互いに素であれば選ぶことができる)、

x\equiv 0\,(\mod n)ならば、f(x)\equiv 0\, (\mod n)が成立する。

そして、x > 0ならば、a\geqq 0, b > 0 であるから、
x - f(x) = 9a +(k+1)b >0
となり、この操作をくりかえすことによって、単調減少列が得られる(その列が負または0となったら終了する、または中学入試なので負になる1つ手前で終了する)。

例えば、7の倍数かどうかを判定したいとき、10\times 2+1 \equiv 0\, (\mod 7)であるから、
x の1の位を消してできる新たな非負整数から、消した 1 の位の2倍を引くという操作

y = ( x / 10 ) - 2 * ( x % 10 )

を繰り返しても 7 の倍数であるということは変わらない。但し、7で割り切れない場合はその余りは変化する。

このアリゴリズムで 14 の次は、-7 となるので、7の倍数であることは保存されているが、最終的な結果は0にならないことに注意しておく。負または0になったときに、その絶対値が7の倍数であれば7の倍数であることは保証されている。

話を元に戻そう。

ここで、n=10k+1とおくと、操作によって nの倍数ことは保存される上に次のことが言える。

(a) a \geqq 0, \, 10 > b > 0により
f(x) = a - kb > -10k > -n
だから、xがnの倍数ならば、 f(x)が負になることはない。

(b) n > 10 だから、 x \geqq nならば操作を行なうことができ、f(x) < x となる。

よって、(a),(b)により、この操作は 0 で終了する。

という訳で、10k+1で割り切れることとkの仲間であることが同値であることがわかる。

算数の問題を解くにはむしろ数学的背景を使わずに単純計算をすれば良いが、一応数学的考察を用いた解説をしておく。

(1) 4567654 が 91 の倍数であることの確認
4567654\to 456729\to 45591 \to 4550\to 455\to 0
となる。ちなみに4567654=91\times 50194 である。

(2) 45676a4404 が 91 の倍数となる a の値を求める問題。
45676a4404 \to 45676a404 \to 45676a04 \to 45676a0 - 36
が 91の倍数で、(1)により45676a0 -36 = 4567654だからa=9
つまり、[オ]=9

(3) 51の倍数で1の位に着目すると、255 または 765 となり、[カ]=2、[キ]=7

(4) 51の倍数は、3の倍数かつ17の倍数であり、34が17の倍数で3+4=7あることに着目すると
34\times 111111111=3777777774=17\times 2\times 3\times 37037037は51の倍数

よって、 a777777774-3777777774=a000000000-3000000000も51の倍数。51と10は互いに素であるから、a-3も51の倍数となり、a=3
つまり、[ク]=3

(5) 間にある333333に着目して、 r333333なる51の倍数を探すと
r333333 \to r33318 \to r3291 \to r324 \to r12 \to [r-1]1
となることから、r=6とすれば良い。
6333333は51の倍数なので2111111は17の倍数。

aa333333bbが3の倍数かつ17の倍数となる条件を考える。
3の倍数である条件からa+bが3の倍数

aa333333bb- 633333300 - b\times 2111111+ b\times 211111100
=aa00000000- 600000000 +b\times 209000000
が17の倍数であるから、
1100\times a - 600 + 209\times b\equiv -5\times(a-b+1)\,(\mod 17)
が17の倍数、よってb\equiv a+1\,(\mod 17)

以上から、(a,\,b)=(1,\,2),(4,\,5),(7,\,8)に限る。