HMMT 二月 2014 · 冲刺赛 · 第 20 题

HMMT February 2014 — Guts Round — Problem 20

[ 11 ] A deck of 8056 cards has 2014 ranks numbered 1–2014. Each rank has four suits—hearts, diamonds, clubs, and spades. Each card has a rank and a suit, and no two cards have the same rank and the same suit. How many subsets of the set of cards in this deck have cards from an odd number of distinct ranks? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT 2014, 22 FEBRUARY 2014 — GUTS ROUND Organization Team Team ID#

解析

[ 11 ] A deck of 8056 cards has 2014 ranks numbered 1–2014. Each rank has four suits—hearts, diamonds, clubs, and spades. Each card has a rank and a suit, and no two cards have the same rank and the same suit. How many subsets of the set of cards in this deck have cards from an odd number of distinct ranks? ( ) 2014 1 2014 2014 Answer: (16 − 14 ) There are ways to pick k ranks, and 15 ways to pick the suits 2 k in each rank (because there are 16 subsets of suits, and we must exclude the empty one). We therefore ( ) ( ) ( ) 2014 2014 2014 1 3 2013 want to evaluate the sum 15 + 15 + · · · + 15 . 1 3 2013 ( ) ( ) ( ) 2014 2014 2014 2014 1 2 2013 2014 2014 Note that (1 + 15) = 1 + 15 + 15 + . . . + 15 + 15 and (1 − 15) = 1 2 2013 ( ) ( ) ( ) 2014 2014 (1+15) − (1 − 15) 2014 2014 2014 1 2 2013 2014 1 − 15 + 15 − . . . − 15 + 15 , so our sum is simply = 1 2 2013 2 1 2014 2014 (16 − 14 ). 2