HMMT 二月 2011 · ALGCALC 赛 · 第 6 题

英文解析

6. 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.