Yesterday’s coincidence

Yesterday I was preparing a lecture where I would need to compute means and standard deviations. I happened to pick five integers x_1, \ldots, x_5 such that their mean and the mean of their squares are both integers. (Alternatively, their sum and the sum of their squares were both multiples of 5.) What are the chances of that?

Incidentally, the integers I chose were 1, 2, 4, 5, 8, so their sum is 1+2+4+5+8 = 20 and their sum-of-squares is 1^2+2^2+4^2+5^2+8^2 = 110, both divisible by 5.

Of course we need some sort of model here. Let’s assume that however we pick integers, they’re uniformly distributed modulo 5 — that is, we have probability 1/5 of choosing a multiple of 5, 1/5 of choosing a number that’s one more than a multiple of 5, and so on. Then the obvious guess is as follows:
(1) the probability that the sum of five randomly chosen integers is divisible by 5 is one-fifth;
(2) the probability that the sum of their squares is divisible by 5 is also one-fifth;
(3) these two events are independent.
As it turns out all of these are true. It’s easy to see that (1) is true. What’s the probability that the sum of n randomly chosen integers is divisible by five? Consider the sum of the first n-1 randomly chosen integers. Whatever this sum is, the probability that we’ll pick an integer that makes the sum of the first n a multiple of five is one-fifth.

However this argument doesn’t work for (2). Look at the squares of the positive integers: they’re 1, 4, 9, 16, 25, and so on. Dividing them by 5 and taking remainders we get 1, 4, 4, 1, 0, 1, 4, 4, 1, 0, \ldots. In fact one-fifth of the squares are divisible by 5; two-fifths are one more than a multiple of five; two-fifths are one less than a multiple of five.

So how could a sum of five squares work out to be a multiple of five? It could consist of:
(A) five multiples of five, like 5^2 + 10^2 + 15^2 + 20^2 + 25^2. This happens with probability 1/5^5.
(B) five squares which are one more than a multiple of 5, like 1^2 + 4^2 + 6^2 + 9^2 + 11^2. This happens with probability (2/5)^5 = 32/5^5.
(C) five squares which are one less than a multiple of 5 — which also happens with probability 32/5^5.
(D) one square which is one more than a multiple of five; one which is one less than a multiple of five; and three multiples of 5, like 1^2 + 2^2 + 5^2 + 10^2 + 15^2 = 355. The probability of this is the number of ways of choosing which of our five integers is one more than a multiple of 5 and which is one less — that’s 5 \times 4 = 20 — times the probability of getting a square that’s one more than a multiple of five, then one that’s one less, then three multiples of 5, which is $(2/5)(2/5)(1/5)^3 = 4/5^5$, for a total of $80/5^5$.
(E) two squares which are one more than a multiple of five; two which are one less; one multiple of five, like 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55. The probability of this is {5 \times 4 \over 2} {3 \times 2 \over 2} (2/5)^4 (1/5) = 480/5^5.

These add up to (1+32+32+80+480)/5^5 = 625/5^5 = 5^4/5^5, or exactly one-fifth! Is there a simple argument for this?

Finally, how can we have a set of integers where both the sum and the sum of squares is a multiple of 5? Working through the cases, the possibilities are either that all five integers have different remainders when dividing by 5, which happens with probability 5!/5^5 = 120/5^5, or that all five have the same remainder, which happens with probability 5/5^5. And these add up to… (120+5)/5^5 = 125/5^5 = 5^3.

As it turns out, though, the sum of five random integers mod 5 and the sum of their squares mod 5 are not independent. Twenty-one of the possible twenty-five outcomes (sum, sum of squares) have probability 1/25. However, (0,1) and (0,4) both have probability $6/125$, and (0,2) and (0,3) both have probability $4/125$. I have no idea why things work out this way, as this is just the result of a brute-force calculation.

Advertisements

5 thoughts on “Yesterday’s coincidence

  1. A couple observations from playing with this problem, for other numbers of integers:

    1. Since the sum of two numbers is even exactly when the sum of their squares is even, these two events won’t be independent in general.

    2. There are only two ways for a sum of four squares to be divisible by four: all four numbers are even, or all four are odd. The probability that this happens is 1/8, not 1/4. I wrote a program to calculate these probabilities: 1/n is the probability that a sum of n squares is divisible by n only if n is 1, 2, 3, 5, 7, 11, 13, 15, or possibly more than 30. I don’t know what these numbers have in common!

    1. Owen, that’s a nice observation about the parity. A bit of simulation I did yesterday gives probabilities near 2/n^2 for the sum and the sum of squares of n integers both being divisible by n, when n is even. In some sense it looks like the parity is the only real constraint.

      Looking at the sequence of numbers you give, I’m kind of reminded of the primes (although why nothing between 15 and 30?) and it wouldn’t surprise me if there’s a characterization of that sequence in terms of prime factorizations. I haven’t had a chance to play with this problem more, though.

    2. I also tried the problem computationally, but unfortunately my results disagree with Owen’s. Specifically, I get that the sum of n squares is divisible by n with probability 1/n if and only if n is 2 or an odd squarefree number.

      I have checked up to n = 500. Our results first disagree at n = 17. I assume that is because 17^17 exceeds the capacity of a 64-bit integer.

  2. הובלות דירות…

    … הובלת דירה – ראשית, עליכם לוודא כי הצעות מחיר ריאליות ולבחור בחברת ההובלות. הובלה בתנאים הובלות דירות, העברת חפצים יקרי ערך וכל פרט בסיסי אחר כמו הימצאותה של בבניין. באתר no problem הובלות ד… Yesterday's coincidence « God plays dice ……

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s