PUMaC 2016 · 代数（A 组） · 第 6 题

PUMaC 2016 — Algebra (Division A) — Problem 6

Let [ a, b ] = ab − a − b . Shaq sees the numbers 2 , 3 , . . . , 101 written on a blackboard. Let V be the largest number that Shaq can obtain by repeatedly choosing two numbers a, b on the board and replacing them with [ a, b ] until there is only one number left. Suppose N is the | V − N ! | 6 integer with N ! nearest to V . Find the nearest integer to 10 · . N ! 2

解析

We can write [ a, b ] = ( a − 1)( b − 1) − 1. Since [[ a, b ] , [ c, d ]] ≤ [[[ a, b ] , c ] , d ] if a > b > c > d , we can maximize V by finding j 101 99 ∏ ∑ ∏ [[ · · · [[101 , 100] , 99] , · · · ] , 2] = ( k − 1) − 2 ( k − 1) − (2 − 1) − 1 . j =2 k =2 k =2 This is perhaps most easily seen by evaluating [[[ a, b ] , c ] , d ] = ( a − 1)( b − 1)( c − 1)( d − 1) − 2( c − 1)( d − 1) − 2( d − 1) − 1 1 and generalizing from there; the general form is j n n − 2 ∏ ∑ ∏ [[ · · · [[ a , a ] , a ] , · · · ] , 2] = ( a − 1) − 2 ( a − 1) − ( a − 1) − 1 . n n − 1 1 k k 1 k =1 j =1 k =1 Clearly the first term, 100!, dominates, so N = 100. So, the desired value becomes 2 · 6 1 1 1 10 ( + + + · · · ) as the remaining terms in the sum are far too small to 100 · 99 100 · 99 · 98 100 · 99 · 98 · 97 1 1 6 4 change our value. In fact, 100 · 99 · 98 · 97 >> 2 · 10 , so we actually wish to find 2 · 10 ( + ). 99 99 · 98 This is just a smidge over 204 . Problem written by Zachary Stier. ∏ 2