HMMT 二月 2007 · 冲刺赛 · 第 34 题
HMMT February 2007 — Guts Round — Problem 34
题目详情
英文原题
- [?] The Game. Eric and Greg are watching their new favorite TV show, The Price is Right . Bob Barkerrecently raised the intellectual level of his program, and he begins the latest installment with biddingon following question: How many Carmichael numbers are there less than 100,000?
Each team is to list one nonnegative integer not greater than 100,000. Let X denote the answer to
Bob’s question. The teams listing N , a maximal bid (of those submitted) not greater than X , willreceive N points, and all other teams will neither receive nor lose points. (A Carmichael number isn − 1
an odd composite integer n such that n divides a − 1 for all integers a relatively prime to n with
1 < a < n .)
解析
英文解析
- [?] The Game. Eric and Greg are watching their new favorite TV show, The Price is Right . Bob Barkerrecently raised the intellectual level of his program, and he begins the latest installment with biddingon following question: How many Carmichael numbers are there less than 100,000?
Each team is to list one nonnegative integer not greater than 100,000. Let X denote the answer to Bob’squestion. The teams listing N , a maximal bid (of those submitted) not greater than X , will receive
N points, and all other teams will neither receive nor lose points. (A Carmichael number is an oddn − 1
composite integer n such that n divides a − 1 for all integers a relatively prime to n with 1 < a < n .)
Answer: 16 ? There are 16 such numbers: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841,
29341, 41041, 46657, 52633, 62745, 63973, and 75361. The next, 101101, is too large to be counted.
Their distribution is considerably more subtle than that of the primes, and it was only recently proven
2 / 7
that there are infinitely many Carmichael numbers. For sufficiently large n , C ( n ) > n , although thisbound has been subsequently improved. (For details, see Alford, W. R.; Granville, A.; and Pomerance,
C. “There are Infinitely Many Carmichael Numbers.” Annals of Mathematics. 139 (1994), 703-722.)
The expectation is that teams are unable to determine that X = 16; otherwise, the obvious dominantplay is listing 16. The Problem Czar, anticipating that teams will attempt to deduce X by consideringthe point values of the other problems in the triplet, has chosen a value X that is considerably lower.
Teams may of course speculate whether this action has been taken, and to what extent, etc... On theactual TV show, many contestants win by guessing prices of 1, or other numbers dramatically lowerthan the actual price. This strategy is enhanced because of the show’s ordered bidding, and will bemore difficult here. It will be interesting to see the submissions.