Probability of selecting two numbers with a sum of squares divisible by 10

Question

Two natural numbers $x$ and $y$ are chosen at random. Find the probability that $x^2 + y^2$ is divisible by 10.

I could not understand how select two numbers from any natural number (infinite).

Answer 1

Your question seems to be more about the correctness of the problem in the first place.

The problem is incorrectly posed. There is no sample space and probability distribution that would make this problem "well posed".

Rather, without warning, what is happening here is different. These problems, without you being told, mean the following:

FIRST, take a very large $N$ and solve the problem for natural numbers picked from $0$ to $N$. Compute the probability, call it $p_N$. Then compute the limit of $p_N$ as $N \to \infty$.

You may be able to solve the problem for $N$ of the form $10k + 9$ (so the number of natural numbers from $0$ to $N-1$ is a multiple of $10$). In that case the answer may actually not depend on $N$. If you don't fuss about all the details, you may claim that that's the answer.

Answer 2

We need to analyze how likely is it that $$ x^2+y^2\equiv0 \mod 10\hspace{2cm}(\star) $$ holds. First note that if it holds for some pair $(x,y)$ then it will hold for $(x+10k,y+10j)$, so we might restrict ourselves to the case $0\leq x,y<10$ and the probability we are looking for is $$ p=\frac{\#\{(x,y):(\star)\text{ and }0\leq x,y<10\}}{\#\{(x,y):0\leq x,y<10\}}. $$ The denominator is clearly $100$. To compute the quantity in the nominator note that $$ (0^2,1^2,2^2,3^2,4^2,5^2,6^2,7^2,8^2,9^2)\mod10=(0,1,4,9,6,5,6,9,4,1). $$ In how many ways can you add two entries of the RHS so that the resulting sum is $0$ or $10$? That is the number we are looking for. It might seem too tedious at first but notice that in order for $a+b$ to be even $a$ and $b$ must have the same parity. Having this into account you should easily find that there are $18$ such ways and so that $$ p=\frac{18}{100}=\frac{9}{50}. $$

---

Edit: [There seems to be some concerns about my answer as it doesn't explicitly address the well-posed issue of the question, so let's be more rigorous:]

As it has been noted by the OP, the first inconvenient one faces with this problem is that we don't know how to pick (with a uniform distribution) a random number in an infinite set like $\mathbb{N}$. The usual way to bypass this is to first solve the problem with the additional restrictions $x,y\in\{0,\ldots,n-1\}$ to get $$p_n=\frac{\#\{(x,y):(\star)\text{ and }0\leq x,y<n\}}{\#\{(x,y):0\leq x,y<n\}},$$ and then (if it exists) take $p_\infty:=\lim_{n\to\infty}p_n$ as the answer. Let's compute $p_n$ then:

It will suffice to compute $p_n$ for $n\geq 10$, so we can write $n=10d+r$ for some $d>0$ and some $0\leq r<10$. Calling $$ N_{j,k}=\#\{(x,y):(\star)\text{ and }10j\leq x<10(j+1),\,10k\leq y<10(k+1)\} $$ we have that $$ (\ast)\,\,\,\,n^2p_n=\underbrace{\#\{(x,y):(\star)\text{ and }\left[10d\leq x<n\text{ or }10d\leq y<n\right]\}}_{=:R}+\sum_{0\leq j,k<d}N_{j,k}. $$ Calculating $R$ explicitly promises to be really tedious, but we can easily bound it; $$ R\leq\sum_{l=0}^{d-1}N_{l,d}+N_{d,d}+\sum_{l=0}^{d-1}N_{d,l}. $$ Now the key point (as you had probably noticed already) is that, exactly by the same argument that the first version of this answer, we have $N_{j,k}=18$ for every pair of indexes $j,k$. Carrying this to $(\ast)$ we obtain $$ 0\leq p_n-\frac{18 d^2}{n^2}=\frac{R}{n^2}\leq\frac{18(2d+1)}{n^2}, $$ which writing $d$ as $d=\lfloor\frac{n}{10}\rfloor$ and taking limits as $n\to\infty$ lets us conclude $$p_\infty=\frac{18}{100}.$$

Answer 3

You are partially right, and partially wrong.

It is impossible to define a uniform probability distribution on the natural numbers (i.e. one where each number has an equal probability of selection).

It is, however, possible to define non-uniform probability distributions on the sample space of all natural numbers. For example, roll a die until you roll a 6, and count how many rolls it took.

For the purpose of this question, you have to kind of take the position of "if there was a uniform distribution over $\mathbb{N}$, and you selected two numbers at random from it, what would be the probability of this property?", which does have a meaningful interpretation - take the sequence of distributions $U_n \sim \mbox{Uniform}(n)$, i.e. where the probability that $U_n = k$ for $k \in \{1, \ldots, n\}$ is $\frac{1}{n}$. Then take two draws $x_n$ and $y_n$ from $U_n$, and consider the probability that $x_n^2 + y_n^2$ is divisible by 10.

Then, consider what happens in the limit as $n \rightarrow \infty$. Does that probability converge to some fixed value? In fact, can you cheat and do the calculation as if the uniform distribution over the naturals existed in the first place? As in, if you do the calculation with $Prob(U_\infty = k) = \frac{1}{\delta}$ for an infinitesimal $\delta$, do all the $\delta$s drop out to give you something vaguely meaningful in the end? The answer is yes, and it's what the other answers to this question are leading you to.

(It would not be guaranteed that the probability would be the same for an arbitrary probability distribution over the natural numbers, which is why you have to assume the somewhat degenerate distribution I described exists.)

Answer 4

Its simple logic. Count numbers on the basis of last digits whose sum of square makes 0.

So Favourable cases = {(0,0),(1,3),(1,7),(2,4),(2,6),(3,1),(3,9),(4,2),(4,8),(5,5),(6,2),(6,8),(7,1),(7,9),(8,4)(8,6),(9,3),(9,7)} = 18

Total cases = Value of x can be any digit from 0 to 9. Similarly for y.

$= 10 * 10 = 100$

$Probability = \frac{\text{No. of favourable cases}}{\text{Total no. of cases}}$

$= \frac{18}{100} = \frac{9}{50} $