返回题库

HMMT 二月 2009 · 冲刺赛 · 第 15 题

HMMT February 2009 — Guts Round — Problem 15

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [ 8 ] Stan has a stack of 100 blocks and starts with a score of 0, and plays a game in which he iteratesthe following two-step procedure:
    (a) Stan picks a stack of blocks and splits it into 2 smaller stacks each with a positive number ofblocks, say a and b . (The order in which the new piles are placed does not matter.)
    (b) Stan adds the product of the two piles’ sizes, ab , to his score.
    The game ends when there are only 1-block stacks left. What is the expected value of Stan’s score at the end of the game?
    12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUNDth

英文原题

[ 8 ] Stan has a stack of 100 blocks and starts with a score of 0, and plays a game in which he iterates
the following two-step procedure:
(a) Stan picks a stack of blocks and splits it into 2 smaller stacks each with a positive number of
blocks, say a and b . (The order in which the new piles are placed does not matter.)
(b) Stan adds the product of the two piles’ sizes, ab , to his score.
The game ends when there are only 1-block stacks left. What is the expected value of Stan’s score at
the end of the game?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 th HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND

解析

英文解析

  1. [ 8 ] Stan has a stack of 100 blocks and starts with a score of 0, and plays a game in which he iteratesthe following two-step procedure:
    (a) Stan picks a stack of blocks and splits it into 2 smaller stacks each with a positive number ofblocks, say a and b . (The order in which the new piles are placed does not matter.)
    (b) Stan adds the product of the two piles’ sizes, ab , to his score.
    The game ends when there are only 1-block stacks left. What is the expected value of Stan’s score at the end of the game?
    Answer: 4950
    Solution: Let E ( n ) be the expected value of the score for an n -block game. It suffices to show that the score is invariant regardless of how the game is played. We proceed by induction. We have E (1) = 0
    and E (2) = 1. We require that E ( n ) = E ( n − k )+ E ( k )+( n − k ) k for all k . Setting k = 1, we hypothesizethat E ( n ) = n ( n − 1) / 2. This satisfies the recursion and base cases so E (100) = 100 · 99 / 2 = 4950.
    th 3
    12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND