0

【東京大学2021年度入試数学(理系)第4問】解答の難しい整数問題

31
0

今回は2021を盛り込んだ整数問題です.今年出題された6問の中でも最も面白い問題です.

問題

以下の問いに答えよ。

  1. 正の奇数 K, L と正の整数 A, BKA=LB を満たしているとする。K4 で割った余りが L4 で割った余りに等しいならば,A4 で割った余りは B4 で割った余りと等しいことを示せ。

  2. 正の整数 a, ba>b を満たしているとする。このとき,A=4a+1C4b+1, B=aCb に対して KA=LB となるような正の整数 K, L が存在することを示せ。

  3. a, b は (2) の通りとし,さらに ab2 の倍数で割り切れるとする。4a+1C4b+14 で割った余りは aCb4 で割った余りと等しいことを示せ。

  4. 2021C374 で割った余りを求めよ。

解答解説

この問題は誘導が良く設計されています.多分,全6問の中で一番面倒な問題であったと思います.が,私はこういう問題の方が得意なので,戦略はすぐにたちました.とはいえ,解答を書くとなると話は別です.

実際,(2) と (3) については長くなってしまったために解答を書き換えました.(オリジナルは感想の後に載せています.)

(1) の解答

この問題は素直に考えましょう.

K, L4 で割った商をそれぞれ p, q, 共通の余りを r とおくと,
K=4p+rL=4q+r
と表すことができます.ここで,KL は奇数であり,rK, L4 で割った余りであるので,r=1 もしくは r=3 となります.

KA=LB より (4p+r)A=(4q+r)B すなわち r(AB)=4(qBpA) となりますが,p, q, r, A, B は全て整数であることから,右辺は 4 の倍数で,r4 は互いに素であるので,AB は4の倍数となります.

すなわち,A4 で割った余りと B4 で割った余りは等しいことが証明されました.

(2) の解答

4a+1C4b+1 を式変形していきます.
4a+1C4b+1=(4a+1)!(4b+1)!×{4(ab)}!=(4a+1)4a(4a1)1(4b+1)4b(4b1)1×4(ab){4(ab)1}1=i=1a(4i)i=1b(4i)×i=1ab(4i)×i=1a{2(2i1)}i=1b{2(2i1)}×i=1ab{2(2i1)}×i=12a+1(2i1)i=12b+1(2i1)×i=12(ab)2(2i1)=i=1aii=1bi×i=1abi×i=1a(2i1)i=1b(2i1)×i=1ab(2i1)×i=12a+1(2i1)i=12b+1(2i1)×i=12(ab)2(2i1)=aCb×i=1a(2i1)i=1b(2i1)×i=1ab(2i1)×i=12a+1(2i1)i=12b+1(2i1)×i=12(ab)2(2i1)
ここで, という見慣れぬ記号が出てきますが,これは の掛け算版です.この記号を使う方が書くのが簡単で,どのように分子分母を分けたかが分かりやすいので使いました.

上の式は要するに,分子分母にある因数(掛け算の構成要素)を「4 の倍数」「4 の倍数ではない偶数」「奇数」に分けて,4 の倍数同士を 4 で,4の倍数ではない偶数同志を 2 で約分しています.

これにより,
K=i=1b(2i1)i=1ab(2i1)i=12b+1(2i1)i=12(ab)(2i1)L=i=1a(2i1)i=12a+1(2i1)
とおくと,KL はそれぞれ奇数であり,上式より A=B×LK すなわち KA=LB が成立するのは明らかなので,これが条件を満たす KL になります.

(3) の解答

K4 で割った余りと L4 で割った余りが等しければ,(1) より命題が成立することになります.

m, n が整数であるとき,

  • (4m+1)(4n+1)=4(4mn+m+n)+1
  • (4m+1)(4n+3)=4(4mn+3m+n)+3
  • (4m+3)(4n+3)=4(4mn+3m+3n+2)+1

したがって,奇数のみからなる積は,積に含まれる 4 で割って 3 余る因数の個数が偶数のときは 4 で割って 1 余り,奇数のときは 4 で割って 3 余ります.よって,K に含まれる 4 で割って 3 余る因数の個数と L に含まれる 4 で割って 3 余る因数の個数の偶奇が等しいことを証明すれば十分となります.

では、KL の因数の中に 4 で割って 3 余る数が何個あるかを数えましょう.

1,3,5,7,4 で割った余りは 1,3,1,3, と交互に現れることから,自然数 n に対して 1,3,,2n1 の中には 4 で割って 3 余る数が [n/2] 個存在します.ここで,[x]x を超えない最大の整数を表します.

以上のことから,4 で割って 3 余る数の個数は次のようになります:

  • 1,3,,2b1 の中には [b/2]
  • 1,3,,2(ab)1 の中には [(ab)/2]=(ab)/2個 (ab2 の倍数より)
  • 1,3,,4b+1 の中には [(2b+1)/2]=b
  • 1,3,,4(ab)1 の中には [2(ab)/2]=ab
  • 1,3,,2a1 の中には [a/2]
  • 1,3,,4a+1 の中には [(2a+1)/2]=a

したがって,KL の中の 4 で割って 3 余る因数の個数をそれぞれ MN で表すと,
M=[b/2]+(ab)/2+b+(ab)N=[a/2]+a
となるので,NM=[a/2][b/2](ab)/2 となります.ここで,ab2 の倍数であることより,ab の偶奇は一致するため,[a/2][b/2]=(ab)/2 となります.したがって,NM=0 すなわち M=N となり,MN の偶奇も一致したため,命題が証明されました.

(4) の解答

単に計算問題です.
2021C374×505+1C4×9+1505C94×126+1C4×2+1126C2=126×12523×13(mod4)
であるので,余りは 3 となります.

感想

小問 (2) と (3) は当初の証明から変更しました.アイデアは同じですが,上記のように KL を直接求める方が記述が簡単になるからです.

ですが,当初の証明の方が私の思考が伝わると思うので,かなり恥ずかしい代物ですが敢えて残しておきます.

しかし,この問題は入試としてはかなりタフだと思います.特に (3) は時間内で解くのが厳しい.(1), (2), (4) くらいが限界のような気がします.

問題としてはなかなかに意欲的で,面白い問題だと思います.少し泥臭いことを要求しますが,このくらいはありだと思いますし,それほど汚い感じはしませんでした.

別解(当初の証明)

(2) の解答

AB が因数として 2 をいくつ持つかを数えれば終わりです.
A=2pLB=2qK
と表すとします.ここで,p, q は非負整数で,L, K は正の奇数であるとします.このとき,p = q が成立すれば KA=LB=2pKL が成り立つので,以下では AB に含まれる 因数 2 の個数が等しいことを示します.

自然数 n に対して n! に含まれる因数 2 の個数を Z(n) とします.このとき,次の補題が成り立ちます.

Z(2n+1)=Z(2n)=Z(n)+n

2n+1 は奇数であるので,Z(2n+1)=Z(2n) は明らかです.1,2,,2n の中で因数 2 を含むのは偶数である 2,4,,2n のみで,これらすべてを 2 で割ると 1,2,,n が得られます.したがって,1n までの中に含まれる因数 2 の個数 Z(n) に,各偶数から 1 個ずつ取り除いた因数 2 の個数の合計 n を加えた数が Z(2n) になります.

ここで、
A=4a+1C4b+1=(4a+1)!(4b+1)!×{4(ab)}!B=aCb=a!b!×(ab)!
であるので、A に含まれる因数 2 の個数 p=Z(4a+1)Z(4b+1)Z(4(ab))B に含まれる因数 2 の個数 q=Z(a)Z(b)Z(ab) となりますが,補題1より
Z(4a+1)=Z(2a)+2a=Z(a)+3aZ(4b+1)=Z(b)+3bZ(4(ab))=Z(ab)3(ab)
であるので,
p=Z(4a+1)Z(4b+1)Z(4(ab))=Z(a)+3aZ(b)3bZ(ab)3(ab)=Z(a)Z(b)Z(ab)=q
が成立し,p=q が証明されました.

(3) の解答

前問より A=2pL かつ B=2pK であることが示されたので,(3) では L に含まれる (A に含まれる) 因数で 4 で割って 3 余る数の個数と,K に含まれる(B に含まれる) 因数で 4 で割って 3 余る数の個数を数えます.ただし、その偶奇だけが等しければ十分です.

というのも,2つの奇数をかけるとき,4 で割った余りの組合せは (1,1), (1,3), (3,1), (3,3)4 通りありますが,(1,1)(3,3) のときは積を 4 で割ると余りが 1 となり,(3,1)(1,3) のときは積を 4 で割ると余りが 3 となります.

ということは,奇数因数の積を 4 で割るとき,4 で割って余りが 3 である因数が偶数個であれば余りが 1 に,奇数個であれば余りが 3 になります.また,割り算に関しても同様です.

小問 (2) と同じように n! に含まれる 4 で割って 3 余る奇数因数の個数の偶奇を X(n) で表します.このとき,次の性質が成り立ちます.

任意の正の整数 n に対して
X(2n)X(n)+[n/2](mod2)X(2n+1)X(n)+[(n+1)/2](mod2)
ここで,[x]x を超えない最大の整数とします.

1,2,,2n を偶奇で分けます.

偶数部分 2,4,,2n に含まれる奇数因数は,これらを 2 で割った 1,2,,n に含まれる奇数因数と等しいため,この中で 4 で割って 3 余る奇数因数の個数の偶奇は X(n) に等しくなります.

一方,奇数部分 1,3,,2n14 で割ると 1,3,1,3, となるので,余りが 3 となる個数は [n/2] となります.

よって,X(2n) の式は正しいことが示されました.X(2n+1) も同様です.

L に含まれる 4 で割って 3 余る因数の個数の偶奇は {X(4a+1)X(4b+1)X(4(ab))}mod2K に含まれる 4 で割って 3 余る因数の個数の偶奇は {X(a)X(b)X(ab)}mod2 であるので,以下では
   X(4a+1)X(4b+1)X(4(ab))X(a)X(b)X(ab)(mod2)
であることを示します.

補題 2 より
X(4a+1)X(2a)+[(2a+2)/2]X(a)+[a/2]+a+1(mod2)X(4b+1)X(b)+[b/2]+b+1(mod2)X(4(ab))X(2(ab))+(ab)X(ab)+[(ab)/2]+(ab)(mod2)
となるので,
   X(4a+1)X(4b+1)X(4(ab))X(a)X(b)X(ab)+[a/2][b/2][(ab)/2](mod2)
ここで,ab2 の倍数であるので,[a/2][b/2]=(ab)/2 かつ [(ab)/2]=(ab)/2 となり,
X(4a+1)X(4b+1)X(4(ab))X(a)X(b)X(ab)+ab2ab2X(a)X(b)X(ab)(mod2)
となります.

したがって,KL4 で割った余りは等しいので,AB4 で割った余りが等しいことが証明されました.

投稿日:202157
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

TomYum君
TomYum君
9
10629
名前はトムヤムクン(TomYumGoong)と読みます.仕事で数学を使う電子・情報系人間.塾講師とは違った立場で気楽に,主に中学入試の算数と大学入試の数学の問題を眺めていこうと思っています.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 問題
  2. 解答解説
  3. (1) の解答
  4. (2) の解答
  5. (3) の解答
  6. (4) の解答
  7. 感想
  8. 別解(当初の証明)
  9. (2) の解答
  10. (3) の解答