数学オリンピック1次予選問題解いてみました ( その5 )
はじめに
今年度 ( 2016年1月 ) のJMO ( 日本数学オリンピック ) の1次予選問題を解いた、その説明の続きです。
最後の方の問題は流石に難しい…!
目次
- 問1 … その1にあります
- 問2 … その1にあります
- 問3 … その3にあります
- 問4 … その1にあります
- 問5 … その3にあります
- 問6 … その2にあります
- 問7 … その2にあります
- 問8 … その4にあります
- 問9 … その2にあります
- 問10 … その4にあります
- 問11 … 今回の記事にあります
- 問12 … ぐぬぬ
解説
例によって、問題文は適宜改変してますので、オリジナルについては冒頭のリンクからご覧ください。
問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後退になっています。
さて。数列の作り方を思い起こしてみると、1～12 は、$+12$の操作で作り出すことができない値です。すなわち、
- その数で数列が始まる ( 初項である )
- ある項の次の項として$-5$して作られる
のいずれか。しかし、初項になれるのはたった1項ですから、ほとんどが後者です。
ここで初項を1としてみます。2～12はより大きい数から$-5$して作られますから…
図の左のように矢印が決まります。この矢印が何を意味するかというと、数列$x_i$の隣り合う項 ( 矢印の向いてる方が後 ) ということですね。そこから数列が「重複する値なく」作れる以上、右の状況まで確定します。すなわち、$x_1$～$x_{18}$が、それぞれ1～18の値の並び替えとして自動的に決まるのです。
そうすると、その続きも考えてみると、今度は18から始めてみるのと同じですから、1～17の周期を繰り返すかっこうになります。この17というのは、$a+b$の値に他なりません。
そしてこの周期の中では値が飛び飛びに変化していますから、結局1～1000まで重複なく値を作るということは、全体がほぼ周期ピッタリに収まっていることを意味します ( $a=12,\,\,b=5$ が適さないのは、周期ピッタリにならないため )。
「ほぼ」というところ、注意が必要です。なぜなら2周期分で見て1～34の場合も、次の周期の始まりを入れて1～35でも、どちらでも重複なく全ての値を辿っているからです。初項が1以外のパターンも見てみると、結局次の図の分を考えれば済むとわかります。
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分程度 ) で仕上げるのはなかなか大変だと思います。
