PUMaC 2022 · 组合（B 组） · 第 4 题

PUMaC 2022 — Combinatorics (Division B) — Problem 4

Ten evenly spaced vertical lines in the plane are labeled ℓ , ℓ , . . . , ℓ from left to right. A set 1 2 10 { a, b, c, d } of four distinct integers a, b, c, d ∈ { 1 , 2 , . . . , 10 } is squarish if some square has one vertex on each of the lines ℓ , ℓ , ℓ , and ℓ . Find the number of squarish sets. a b c d

解析

Ten evenly spaced vertical lines in the plane are labeled ℓ , ℓ , . . . , ℓ from left to right. A set 1 2 10 { a, b, c, d } of four distinct integers a, b, c, d ∈ { 1 , 2 , . . . , 10 } is squarish if some square has one vertex on each of the lines ℓ , ℓ , ℓ , and ℓ . Find the number of squarish sets. a b c d Proposed by Ben Zenker Answer: 50 Without loss of generality, assume that a < b < c < d . Then, it is easy to see that { a, b, c, d } is squarish if and only if the distance between ℓ and ℓ equals the distance between ℓ and ℓ . In a b c d other words, we must count the number of subsets { a, b, c, d } of { 1 , 2 , . . . , 10 } with d − c = b − a . To do this, we proceed by casework on k = d − c . • If k = 1, we find that for each value of d , the maximum possible value for a is d − 3, so there are d − 3 possible combinations of the four numbers. Then, d ranges from 4 to 10 inclusive, for a total of 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 combinations. • If k = 2, each value of d gives d − 5 possible combinations. Then, d ranges from 6 to 10 inclusive, for a total of 5 + 4 + 3 + 2 + 1 = 15 combinations. • If k = 3, each value of d gives d − 7 possible combinations. Then, d ranges from 8 to 10 inclusive, for a total of 3 + 2 + 1 = 6 combinations. • If k = 4, there is only 1 combination a = 1 , b = 5 , c = 6 , d = 10. Summing yields a total of 28 + 15 + 6 + 1 = 50 sets { a, b, c, d } .