HMMT 二月 2011 · ALGCALC 赛 · 第 6 题

HMMT February 2011 — ALGCALC Round — Problem 6

Let a ? b = ab + a + b for all integers a and b . Evaluate 1 ? (2 ? (3 ? (4 ? . . . (99 ? 100) . . . ))).

解析

Let a ? b = ab + a + b for all integers a and b . Evaluate 1 ? (2 ? (3 ? (4 ? . . . (99 ? 100) . . . ))). Answer: 101! − 1 We will first show that ? is both commutative and associative. • Commutativity: a ? b = ab + a + b = b ? a • Associativity: a ? ( b ? c ) = a ( bc + b + c ) + a + bc + b + c = abc + ab + ac + bc + a + b + c and ( a ? b ) ? c = ( ab + a + b ) c + ab + a + b + c = abc + ab + ac + bc + a + b + c . So a ? ( b ? c ) = ( a ? b ) ? c . So we need only calculate (( . . . (1 ? 2) ? 3) ? 4) . . . ? 100). We will prove by induction that (( . . . (1 ? 2) ? 3) ? 4) . . . ? n ) = ( n + 1)! − 1 . • Base case ( n = 2): (1 ? 2) = 2 + 1 + 2 = 5 = 3! − 1 • Inductive step: Suppose that ((( . . . (1 ? 2) ? 3) ? 4) . . . ? n ) = ( n + 1)! − 1 . Then, (((( . . . (1 ? 2) ? 3) ? 4) . . . ? n ) ? ( n + 1)) = (( n + 1)! − 1) ? ( n + 1) = ( n + 1)!( n + 1) − ( n + 1) + ( n + 1)! − 1 + ( n + 1) = ( n + 2)! − 1 Algebra & Calculus Individual Test Hence, (( . . . (1 ? 2) ? 3) ? 4) . . . ? n ) = ( n + 1)! − 1 for all n . For n = 100, this results to 101! − 1.