Conference rusure::math

1417.0. "Guessing Pi's Digits" by JARETH::EDP (Always mount a scratch monkey.) Wed Apr 10 1991 10:49

Article 16673 of sci.math:
Path: shlump.nac.dec.com!rust.zso.dec.com!pa.dec.com!decwrl!apple!mips!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!cbnewsl!rfm
From: rfm@cbnewsl.att.com (robert.a.mayans)
Newsgroups: sci.math,rec.puzzles
Subject: Guessing the digits of pi -- SOLUTION
Message-ID: <1991Apr9.163750.25050@cbnewsl.att.com>
Date: 9 Apr 91 16:37:50 GMT
Followup-To: poster
Organization: AT&T Bell Laboratories
Lines: 75
Xref: shlump.nac.dec.com sci.math:16673 rec.puzzles:8635


   The problem I posted a week ago was to find a winning strategy for
   the following game.  You are playing against a supercomputer that
   can calculate the digits of pi far beyond what we are currently
   capable of doing.  This computer selects a position in the
   decimal expansion of pi -- say, at 10^100.  Your job is to guess
   what the next digit or digit sequence is.  Specifically, you
   have one dollar to bet.  A bet on the next digit, if correct,
   returns 10 times the amount bet; a bet on the next two digits
   returns 100 times the amount bet, and so on.  (The dollar may
   be divided in any fashion, so we could bet 1/3 or 1/10000 of
   a dollar.)  You may place bets in any combination.  The computer
   will tell you the position number, let you examine the digits
   up to that point, and calculate statistics for you.

   It is easy to set up strategies that might win, if the supercomputer
   doesn't know your strategy.  For example, "Always bet on 7" might
   win, if you are lucky.  Also, it is easy to set up bets that will
   always return a dollar.  For example, if you bet a penny on every
   two-digit sequence, you are sure to win back your dollar.  Also,
   there are strategies that might be winning, but we can't prove it.
   For example, it may be that a certain sequence of digits never
   occurs in pi, but we have no way of proving this.

   The problem is to find a strategy that you can prove will always win
   back more than a dollar.

   The assumption that the position is beyond the reach of calculation
   means that we must rely on general facts we know about the sequence
   of digits of pi, which is practically nil.  But it is not completely
   nil, and the challenge is to find a strategy that will always win
   money.

   There seemed to be no takers, so here is the SOLUTION:







   A theorem of Mahler (1953) states that for all integers p, q > 1,

                    -42
      |pi - p/q| > q

   This says that pi cannot have a rational approximation that is
   extremely tight.

   Now suppose that the computer picks position N.  I know that the next
   41 * N digits cannot be all zero.   For if they were, then the first
   N digits, treated as a fraction with denominator 10^N, satisfies:

      |pi - p / 10^N|  <  10^(-42 N)

   which contradicts Mahler's theorem.

   So, I split my dollar into 10^(41N) - 1 equal parts, and bet on
   each of the sequences of 41N digits, except the one with all
   zeroes.  One of the bets is sure to win, so my total profit
   is about 10(^-41N) of a dollar!

   This strategy can be improved a number of ways, such as looking for
   other repeating patterns, or improvements to the bound of 42 -- but
   the earnings are so pathetic, it hardly seems worth the effort.

   Are there other winning strategies, not based on Mahler's theorem?
   I believe there are algorithms that generate 2N binary digits of
   pi, where the computations are separate for each block of N digits.
   Maybe from something like this, we can find a simple subsequence of
   the binary digits of pi which is always zero, or which has some
   simple pattern.

   -- Bob Mayans, AT&T Bell Labs
      rfm@whscad1.att.com

I would like very much to see a proof of said theorem.