PUMaC 2023 · 组合（A 组） · 第 3 题

PUMaC 2023 — Combinatorics (Division A) — Problem 3

The integers from 1 to 25, inclusive, are randomly placed into a 5 by 5 grid such that in each row, the numbers are increasing from left to right. If the columns from left to right are numbered 1, 2, 3, 4, and 5, then the expected column number of the entry 23 can be written a as where a and b are relatively prime positive integers. Find a + b . b

解析

The integers from 1 to 25, inclusive, are randomly placed into a 5 by 5 grid such that in each row, the numbers are increasing from left to right. If the columns from left to right are numbered 1, 2, 3, 4, and 5, then the expected column number of the entry 23 can be written a as where a and b are relatively prime positive integers. Find a + b . b Proposed by Rishi Dange Answer: 17 14 The answer is . We proceed using casework, seeing pretty easily that 23 cannot be in columns 3 1 or 2. Case 1: 23 is in column 5 In a given row, by putting 23 as the rightmost item, there are now 22 ( ) 22 4 ways to fill in the rest of the row. This makes for a probability of 5 rows × . 25 4 ( ) 5 Case 2: 23 is in column 4 The right two elements in the row with 23 are either 23 and 24 or 23 and 25, which makes the “rows” coefficient above 5 × 2 = 10. Thus we now have a probability 22 ( ) 3 of 10 × . 25 ( ) 5 Case 3: 23 is in column 3 The right three elements must be 23, 24, and 25, so the coefficient is 22 ( ) 2 5 again to represent the number of possible rows. Thus we now have a probability of 5 × . 25 ( ) 5 Computing the expected value using these probabilities (quite a bit of stuff cancels out), we 14 find the expected value to be . 3