読者です 読者をやめる 読者になる 読者になる

数学オリンピック1次予選問題解いてみました ( その5 )

はじめに

今年度 ( 2016年1月 ) のJMO ( 日本数学オリンピック ) の1次予選問題を解いた、その説明の続きです。
最後の方の問題は流石に難しい…!

目次

解説

例によって、問題文は適宜改変してますので、オリジナルについては冒頭のリンクからご覧ください。

問11

問題

  • (a,b)の組 ( a,bは共に2以上の整数 ) の中で、次の条件を満たす数列$x_1,x_2,\cdots,x_{1000}$が存在するものは何組あるか求めよ。
  • $x_1,x_2,\cdots,x_{1000}$は$1,2,\cdots,1000$の並び替えである
  • 各i ( $1\leq i\lt 1000$, iは整数 ) に対して、$x_{i+1}=x_i+a$ もしくは $x_{i+1}=x_i-b$ のいずれかが成立する

解説

答えは2940です。

まず問題がわけわかりませんね。「数列が存在する」「並び替え」って何?? ってところから。これは3番目の条件と合わせて、次のように読み替えるとしっくりきます。

  • 初項$x_1$を適切に定め、2項目以降を$x_{i+1}=x_i+a$ もしくは $x_{i+1}=x_i-b$ とすることで、次の条件を満たす数列$x_i\,( 1\le i\le 1000 )$を作り出すことができる
  • $x_i$は1~1000の整数値を、重複なく1項ずつ含む ( 1~1000以外の値は含まない )

また、a,b が互いに素であることはほぼ自明ですから、同時に$a\neq b$でもあります。

ということで、実際に数列を作りを試してみて、法則性を見てみます。

数列の例

では、前提として$a\gt b$を仮定し、$a=12,\,b=5$の例で試してみます ( これは実は条件を満たさないのですが )。

見易いように、5で割った余りで分類してみると、$+12$は異なる余りへの幾つかの前進、$-5$は同じ余りへの1後退になっています。

f:id:ange1:20160303173324p:plain

さて。数列の作り方を思い起こしてみると、1~12 は、$+12$の操作で作り出すことができない値です。すなわち、

  • その数で数列が始まる ( 初項である )
  • ある項の次の項として$-5$して作られる

のいずれか。しかし、初項になれるのはたった1項ですから、ほとんどが後者です。
ここで初項を1としてみます。2~12はより大きい数から$-5$して作られますから…

f:id:ange1:20160303180432p:plain

図の左のように矢印が決まります。この矢印が何を意味するかというと、数列$x_i$の隣り合う項 ( 矢印の向いてる方が後 ) ということですね。そこから数列が「重複する値なく」作れる以上、右の状況まで確定します。すなわち、$x_1$~$x_{18}$が、それぞれ1~18の値の並び替えとして自動的に決まるのです。

そうすると、その続きも考えてみると、今度は18から始めてみるのと同じですから、1~17の周期を繰り返すかっこうになります。この17というのは、$a+b$の値に他なりません。

f:id:ange1:20160303205951p:plain

そしてこの周期の中では値が飛び飛びに変化していますから、結局1~1000まで重複なく値を作るということは、全体がほぼ周期ピッタリに収まっていることを意味します ( $a=12,\,\,b=5$ が適さないのは、周期ピッタリにならないため )。

「ほぼ」というところ、注意が必要です。なぜなら2周期分で見て1~34の場合も、次の周期の始まりを入れて1~35でも、どちらでも重複なく全ての値を辿っているからです。初項が1以外のパターンも見てみると、結局次の図の分を考えれば済むとわかります。

f:id:ange1:20160303185323p:plain

2~11が初項のパターンは周期ピッタリなので省略しています。初項が1~12以外はちょっと特殊で、1周期しか許容されませんが、これも周期ピッタリの1種とみなすことができます。見落としがち ( まあ私が、ですが ) なのは一番右のケース。最初の周期のみ1少なくなるのです ( 1~33でも重複なく全ての値を辿っている )。

これで条件がわかりました。

  • 1~1000 が、周期$a+b$ぴったり、もしくは±1になっていること。

あ。$a\gt b$を前提としていたのを忘れていました。が、$a\lt b$のケースは、数字の大小ひっくり返せば全く同じお話になります。なので、この前提は無くしてしまって構いません。

計算本番

さて、それでは計算です。条件を再度、数式としてまとめると、

  • $a\gt 1,\,\,b\gt 1$
  • $a,b$は互いに素
  • $a+b$が999,1000,1001いずれかの約数

ということになります。ここで、999,1000,1001はどれをとっても同じ素因数を持っていませんから、独立して考えることができます。

…しかし、互いに素で、合計が約数で…。一体幾つ場合分けすれば…。
ここで発想を転換すると楽になります。すなわち、

  • $A+B=999,1000,1001\,\,( A\ge 1,\,\,B\ge 1 )$
  • $a=\frac{A}{g},\,\,b=\frac{B}{g}\,\,( g=\gcd(A,B) )$
  • $A\neq g,\,\,B\neq g$

999,1000,1001のいずれかを分割してA,Bとし、それを最大公約数で割ってa,bを作れば、それが条件を満たすはずです。ただし、最後の条件を考慮すると「AもしくはB自身が約数である場合」を除いて、です ( $g$は$A+B=999,1000,1001$の約数であることに注意 )。

999,1000,1001それぞれ、1~998,1~999,1~1000の範囲の約数の個数は7,15,7です。A,Bどちらかが約数ということで倍に換算すると、答えは $998+999+1000-(7+15+7)\times 2=2939$ と計算できます。

…あれ?? なんかおかしいですね。$a\gt b,\,\,a\lt b$のケースと対称のはずなのになぜ答えが奇数になっているのでしょう。

実は、約数の個数を倍に換算した時、$A=B=500$のケースを二重に引いてしまったことになっています。なので、$+1$の補正が必要です。ということで、$998+999+1000-(7+15+7)\times 2+1=2940$ が正しい、となります。

続く?

いや流石に最後の方の問題は難しいですね。実のところ、問11は正しい答えを出すまで何度も見落としで間違えました。これを本番の短い時間 ( せいぜい20分程度 ) で仕上げるのはなかなか大変だと思います。