MathLabs

第1問

正の整数 n に対し、x と y が非負整数で x+y<n を満たす点 (x,y) 全体を T とする。T の各点を赤または青に塗り、(x,y) が赤なら、第一座標が x 以下、第二座標が y 以下のすべての点も赤とする。x 座標が互いに異なる n 個の青点の選び方を A、y 座標が互いに異なる n 個の青点の選び方を B とする。A=B を証明せよ。 nn TT (x,y)(x,y) xx yy x+y<nx+y<n TT (x,y)(x,y) TT xx yy AA nn xx BB nn yy A=BA=B
ステップ 2/3: 赤点を一つずつ除く
ざっくり言うと

対応する除去を行いながら左下の赤いイデアルを構成する。

ax=by=n−x−y−1a_x=b_y=n-x-y-1
詳しい解説

最初はすべてを青とする。赤い下位イデアルを、各点の右上側がすでに処理される逆位相順で構成する。 を赤に変えると、その列と行に残る青点はともに 個であり、二つの多重集合から同じ数を除くことになる。初めは両方とも なので、最後まで一致する。 (x,y)(x,y) n−x−y−1n-x-y-1 {1,2,…,n}\{1,2,\ldots,n\}