ジュニア数学オリンピックの簡単な問題（５８）

こんにちは。東久留米市の学習塾塾長です。

昨日に続いて、今日も晴れのいい天気になりました。９月になり、空の雲は秋仕様になってきましたが、日向では汗ばむほどの陽射しです。これから過ごしやすい季節が始まります。受験生の皆さんは大いに勉強してください。

さて、今回は２０１６年ジュニア数学オリンピック予選に出題された整数問題を取り上げます。

問題は、
「各桁の数字が相異なるような３７の倍数のうち、最大のものを求めよ。」
です。

初めに、３７の倍数について調べておきましょう。

ある正の整数Ｎを末桁から３桁ずつ区切り、それらを順に、Ａ0、Ａ1、・・・Ａn-1、Ａn　とすると、Ｎは、

と表すことができます。

一方、

なので、Ｎを３７で割った余りは、

を３７で割った余りと等しくなります。

つまり、Ｎが３７の倍数のとき、Ｎを末桁から３桁ずつ区切って作った数の和が３７の倍数になります。

それでは、問題に戻りましょう。

各桁の数字が相異なる数で最大のものは、９８７６５４３２１０です。

これが３７の倍数であれば手間はないのですが、９８７６５４３２１０÷３７＝２６６９３３６００・・・１０と、３７の倍数ではありません。

そこで、与えられた３つの条件（３７の倍数、各桁の数字が相異なる、最大の数）を満たす数を探すわけですが、このとき、最大の数という条件に注目して、９８７６５４３２１０に近い数から探すことにしましょう。

ここで、先ほどの３７の倍数の性質を思い起こすと、３７の倍数は末桁から３桁ずつ区切って作った数の和が３７の倍数になるのでしたから、９８７６５４３２１０に近い９８７６５４３＊＊＊が３７の倍数になるかを調べることにしましょう。（＊は、０、１、２です）

初めに調べた３７の倍数の性質から
９８７６５４３＊＊＊が３７の倍数になるのは、
９＋８７６＋５４３＋＊＊＊＝１４２８＋＊＊＊
　　　　　　　　　　　　　　　　＝３７・３８＋２２＋＊＊＊
から、２２＋＊＊＊が３７の倍数になるときです。

ここで、＊は、０、１、２なので、
＊＊＊＝２１０、２０１、１２０、１０２、０２１、０１２
で、
２２＋＊＊＊＝２３２、２２３、１４２、１２４、４３、３４
になりますが、このなかに３７の倍数はありません。

つまり、９８７６５４３＊＊＊で表される数には問題の条件を満たすものはないということが判りました。

それでは、次に、９８７６＊＊＊＊＊＊で表される数について調べましょう。末桁から３桁の数をＰ、次の３桁の数をＱとすると、９８７６＊＊＊＊＊＊が３７の倍数になるのは、
９＋８７６＋Ｑ＋Ｐ＝８８５＋Ｐ＋Ｑ
　　　　　　　　　　　＝３７・２３＋３４＋Ｐ＋Ｑ
から、３４＋Ｐ＋Ｑが３７の倍数になるときです。

ここで、Ｐ、Ｑはそれぞれ３桁（先頭が０のときも含む）で、それらの合わせて６個の数は、０、１、２、３、４、５なので、Ｐ＋Ｑの最大値は、ＰとＱの百の位が５と４、十の位が３と２、一の位が１と０になるときで、それは９５１です。

同様に、Ｐ＋Ｑの最小値は、ＰとＱの百の位が１と０、十の位が３と２、一の位が５と４になるときで、それは１５９です。

したがって、３４＋Ｐ＋Ｑは、
１９３≦３４＋Ｐ＋Ｑ≦９８５　　　　　　　　（★）
で、これを満たす３７の倍数で、０、１、２、３、４、５を１回ずつ使った３桁の数が存在するかを調べることになります。

そこで、（★）を満たす３７の倍数を書き上げると、
２２２、２５９、２９６、３３３、３７０、４０７、４４４、４８１、５１８、５５５、５９２、６２９、６６６、７０３、７４０、７７７、８１４、８５１、８８８、９２５、９６２
で、Ｐ＋Ｑは、
１８８、２２５、２６２、２９９、３３６、３７３、４１０、４４７、４８４、５２１、５５８、５９５、６３２、６６９、７０６、７４３、７８０、８１７、８５４、８９１、９２８
になります。

ここで、ＰとＱは、０、１、２、３、４、５を１回ずつ使った３桁の数なので、それらの和に、一回も現れない数字は０、２回以上は現れない数字は１、２、８、９です。

また、同時に現れない数字の組合せは、１と２、１と３、１と４、２と３、６と９、７と８、７と９、８と９です。

これらを使って、上のリストから該当しないものを取り除くと、
３３６、３７３、４４７、４８４、５５８、５９５、６３２、７４３、８５４
になります。

さらに、ＰとＱの足し算で、繰り上がりが起こらないことを利用して、上の９個の数を片っ端に調べていきましょう。

３３６、３７３は、ＰとＱの２つの位の数字が０、１、２、３で、残った数字は、４と５になります。ところが、４＋５＝９≠６、７なのでＮＧです。

４４７は、ＰとＱの百と十の位の数字が０、１、３、４で、残った数字は、２と５になります。このとき、２＋５＝７なので、４４７はＯＫで、４８４はＮＧです。

５５８、５９５は、ＰとＱの２つの位の数字が０、１、４、５と０、２、３、５と１、２、３、４の３通りで、それぞれの場合で残った数の和は、２＋３＝１＋４＝０＋５＝５≠８なのでＮＧです。

６３２は、ＰとＱの一の位の数字が０、２で、残った数字は、１、３、４、５になります。ところが、これらの数字から６３２の十の位の３を作ることができないのでＮＧです。

７４３は、ＰとＱの百の位の数字が２、５と３、４の２通りで、それぞれの場合で残った数字は、０、１、３、４と０、１、２、５です。ところが、これらの組合せで７４３の十と一の位の３と４を同時に作ることはできないのでＮＧです。

８１７は、ＰとＱの百と一の位の数字がそれぞれ３、５と３、４で、これらを同時に作ることができないのでＮＧです。

８５４は、ＰとＱの百の位の数字が３、５で、残った数字は、０、１、２、４です。ところが、これらの数字から８５４の十と一の位の５と４を同時に作ることができないのでＮＧです。

以上で、問題の条件を満たすＰ＋Ｑは４４７であることが判りました。

そして、Ｑ＝４３５、Ｐ＝０１２としたとき、９８７６ＱＰは最も大きくなり、したがって、９８７６４３５０１２が答えです。


最後の候補をふるいにかけるところが煩雑です。もう少し上手い方法があるかもしれないです。ご存知の方はご教示ください。面白い問題でした。