34. [?] The Game. Eric and Greg are watching their new favorite TV show, The Price is Right. Bob Barker recently raised the intellectual level of his program, and he begins the latest installment with bidding on 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$, will receive $N$ points, and all other teams will neither receive nor lose points. (A Carmichael number is an odd composite integer $n$ such that $n$ divides $a^{n-1}-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 that there are infinitely many Carmichael numbers. For sufficiently large $n, C(n)>n^{2 / 7}$, although this bound 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 dominant play is listing 16. The Problem Czar, anticipating that teams will attempt to deduce $X$ by considering the 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 the actual TV show, many contestants win by guessing prices of 1 , or other numbers dramatically lower than the actual price. This strategy is enhanced because of the show's ordered bidding, and will be more difficult here. It will be interesting to see the submissions.