Wikipedia:Reference desk/Archives/Mathematics/2009 July 13

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 13

Points on square grid

I presume that this is a well-known result, but I couldn't find it. What is the greatest number of points which can be marked on an n by n square grid so that no three are collinear? Drawing successive cases suggests that for n=0, 1, 2, 3 and 4, the answer is 0, 1, 4, 5 and 6 - is this correct so far, and what's the general result?—86.132.235.208 (talk) 18:21, 13 July 2009 (UTC)

You're wrong with the last two values: for n=3, the answer is 6 (take all except one diagonal) and for n=4, it's 8 (take the inner two of each side of the square). For arbitrary n, the number can be no higher than 2n (since every line or column can only contain two marked points), but I'm not sure if this value can always be achieved for n>4 (for n=5, I get no further than 9 marked points). --Roentgenium111 (talk) 22:02, 13 July 2009 (UTC)

10 points are possible for $n=5$:

**---
*--*-
---**
-**--
--*-*

For $n=6$, 12:

**----
---*-*
-*--*-
*-*---
----**
--**--

And it does not seem completely implausible that this generalizes to every n. -- Meni Rosenfeld (talk) 15:29, 14 July 2009 (UTC)

Some Google-fu turned up this summary from Research Problems in Discrete Geometry by Peter Brass, W. O. J. Moser, János Pach, p417: "In a long sequence of papers ... many examples were constructed, up to n = 52, for which the bound 2n is obtained. Most of these sets were found by computer search and no general pattern has emerged". Gandalf61 (talk) 16:22, 14 July 2009 (UTC)

Average of the first billion digits of the decimal expansion of Pi

Is it possible to know what the answer to that is - in which case what is it and how did you work it out - without laboriously adding them up? -- JackofOz (talk) 20:58, 13 July 2009 (UTC)

In other words, you add the numeral values of the digits and divide by 1,000,000,000? If that's what you mean, couldn't you just put them all into a spreadsheet? Nyttend (talk) 21:02, 13 July 2009 (UTC)

Do you want an exact answer? I doubt there's any clever trick to speed this calculation up faster than simply adding up the digits. (Well, actually there is — just print out the right answer. But I suppose you want a justified method.)

On the other hand, if you're OK with an answer that's good to 3 or 4 decimal digits, the answer is 4.5 . --Trovatore (talk) 21:09, 13 July 2009 (UTC)

That's close enough. Thanks for the quick responses. -- JackofOz (talk) 21:18, 13 July 2009 (UTC)

Using the table here, the first billion digits of $\pi -3$ add up to 4500057062. Also to be found in this OEIS sequence. Fredrik Johansson 21:28, 13 July 2009 (UTC)

"Trovatore" didn't really state his answer except for its bottom line number. Here's the rest: The average of the ten digits 0 through 9 is

(0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)/10 = 45/10 = 4.5.

That's Trovatore's answer.

That's approximately correct if the ten digits occur equally frequently in the long run. But here's a hard question: Do the ten digits really occur equally frequently?

For that we have only statistical evidence, not a mathematical proof.

In one sense, the answer is clearly "no": if the sum is 4500057062 instead of 4500000000 (i.e. 4.5 billion) then it deviates slightly from exact equality. But it is conjectured that you can get as close as you want to equality of those ten frequencies by making the number of digits big enough.

If you want to get into statistical evidence, then we'd also talk about pairs of consecutive digits, and triples of consecutive digits, and so on. The number cited above, 4500057062, does not deviate from 4.5 billion by more than would be predicted by the full-fledged conjecture dealing with pairs, triples, etc. occurring equally frequently. One could get into details of how that conclusion was reached as well.

But the way Trovatore came up with 4.5 is just that it's the average of the ten digits 0 through 9. Michael Hardy (talk) 23:25, 13 July 2009 (UTC)

It is conjectured but unproven that pi is a normal number (Trovatore's answer being wrong would have been interesting evidence against the conjecture). However, if you just want the billionth digit without having to compute all the preceding ones, there is a beautiful spigot algorithm for obtaining it, at least if you don't mind a hexadecimal rather than decimal expansion. 70.90.174.101 (talk) 01:08, 14 July 2009 (UTC)

I'm supremely indifferent to what the billionth digit is, but thanks anyway. I was too naive in accepting Trovatore's answer as the answer to the question I asked. It's probably very close to 4.5, but just for the fun of it, can anyone produce the actual average I'm seeking, to, say, 9 decimal places? -- JackofOz (talk) 09:23, 14 July 2009 (UTC)

4.500057062 - see Fredrik Johansson's response above. Gandalf61 (talk) 09:46, 14 July 2009 (UTC)

Why were you "too naive"? I was right, wasn't I? --Trovatore (talk) 21:46, 14 July 2009 (UTC)

Note that Trovatore's answer was right even wrto the precision: tree or four decimal digits. --pma (talk) 14:26, 15 July 2009 (UTC)

Randomly choosing one object out of a countably infinite set

During a physical-world discussion of a subject that has caused much distress here, the person I was discussing it with suggested that it would be much easier to look at from the point of view of picking a door from an infinite set of doors. This has caused me great distress independent of the problem. Let's look at the odds of randomly selecting one element from N with equal probability, that is P(1) = P(k), for any k in N. By the definition of probability, P(1) is either 0 or an element of (0..1]. The sum of all P(x) (=P(1)), x in N, equals 1, and by the Archimedian principle, if P(1) > 0, there exists some n such that P(1) * n < 1, so P(1) = 0. Thus P(1..n) = n * P(1) = 0, and the limit as n goes to infinity of 0 is 0. The only conclusion I can come to is that it's not meaningful to speak of selecting an element from N with equal probability?!? I'm not sure what I'm missing here, but I think I'm missing something.--Prosfilaes (talk) 23:17, 13 July 2009 (UTC)

You're missing nothing. There is no uniform countably additive probability measure on the natural numbers. Algebraist 00:07, 14 July 2009 (UTC)

In many cases, such as the German tank problem, a probability distribution f(k)=1/Ω, for k=1...Ω, and f(k)=0 elsewhere, for some large value of Ω, may serve as a prior distribution. After computation of a posterior distribution you may take the limit of infinite Ω. It is incorrect to take the limit first and compute afterwards. Bo Jacoby (talk) 10:15, 14 July 2009 (UTC).

As a consequence of what is stated in the first reply, if you want the distribution to be uniform you have to renounce to countably additivity. There are translation invariant, finitely additive probability measures in N; they are all in the dual of l^∞. -pma (talk) 16:13, 14 July 2009 (UTC)