令和6年度 秋期 午前 問6

✓ これが正解イa−b が n の倍数

解説

余りが等しいことは差が割り切れることです。

設問は、キーを表の大きさで割った余りを置き場所とするハッシュ関数のもとで、二つのキーが衝突する条件を選ばせています。衝突するとは、二つのキーが同じ置き場所に落ちること、すなわち表の大きさで割った余りが等しいことです。ある数を割った余りが等しい二つの数は、その差がちょうど割り切れます。逆に差が割り切れるなら余りは等しくなります。したがって条件は、二つのキーの差が表の大きさの倍数であることです。表の大きさを 7 として確かめます。10 と 3 は余りがどちらも 3 で同じ場所に落ち、差の 7 は 7 で割り切れます。10 と 5 は余りが 3 と 5 で別の場所に落ち、差の 5 は 7 で割り切れません。ここで気をつけたいのは、二つのキーを足すのか引くのか、そしてどちらがどちらで割り切れるのかという向きです。倍数という言い方は、前に置いた数が後ろの数で割り切れることを表すので、前後を取り違えると条件が反対になります。

ほかの選択肢はなぜ違うのか

• アa＋b が n の倍数：二つのキーの和が表の大きさの倍数という条件です。表の大きさを 7、キーを 10 と 4 とすると和の 14 は 7 で割り切れますが、余りは 3 と 4 で異なり同じ場所には落ちません。反例が作れるので条件になりません。
• ウn が a＋b の倍数：表の大きさのほうが二つのキーの和で割り切れるという条件です。足している点と、割り切れる向きが逆になっている点の二つが誤っており、表の大きさが和より小さければそもそも成り立ちません。
• エn が a−b の倍数：表の大きさのほうが二つのキーの差で割り切れるという条件です。差に着目するところまでは合っていますが向きが逆で、表の大きさを 7、差を 14 とすると 7 は 14 で割り切れないのに余りは等しくなります。