第1問

正の整数 n に対し、x と y が非負整数で x+y<n を満たす点 (x,y) 全体を T とする。T の各点を赤または青に塗り、(x,y) が赤なら、第一座標が x 以下、第二座標が y 以下のすべての点も赤とする。x 座標が互いに異なる n 個の青点の選び方を A、y 座標が互いに異なる n 個の青点の選び方を B とする。A=B を証明せよ。

n

T

(x,y)

x

y

x+y<n

T

(x,y)

T

x

y

A

n

x

B

n

y

A=B

ステップ 3/3: 積を取る

前のステップ次のステップ

ざっくり言うと

等しい多重集合から二つの積の等式を得る。

A=\prod_{x=0}^{n-1}a_x=\prod_{y=0}^{n-1}b_y=B

詳しい解説

異なる座標を持つ選び方は各列から一つずつ選ぶことであり、異なる座標の場合は各行から一つずつ選ぶことである。多重集合が等しいため、となる。 $x$ $y$ $A=B$