PUMaC 2014 · 组合（B 组） · 第 2 题

PUMaC 2014 — Combinatorics (Division B) — Problem 2

[ 3 ] A 100 × 100 grid is given as shown. We choose a certain number of cells such that exactly two cells in each row and column are selected. Find the sum of numbers in these cells.

解析

[ 3 ] A 100 × 100 grid is given as shown. We choose a certain number of cells such that exactly two cells in each row and column are selected. Find the sum of numbers in these cells. Solution: We see that entry in row i column j will be 100( i − 1) + j = a + b . Since each column and i j ∑ ∑ 100 100 each row contains exactly two cells choosen, we see that the sum is 2 a + 2 b = i j i =1 j =1 ∑ ∑ ∑ 100 100 100 200( i − 1)+ 2 j = 202 i − 200 × 100 = 202 × 100 × 101 / 2 − 200 × 100 = 1000100 i =1 j =1 i =1