9
$\begingroup$

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).

$\endgroup$
16
$\begingroup$

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}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain without the term mod $\endgroup$ – user123733 Dec 12 '16 at 3:52
  • 2
    $\begingroup$ $x\equiv y\mod m$ means that $x=y+mk$ for some $k\in\mathbb{Z}$. One could translate this answer using this so that the result does not use modular arithmetic, but honestly learning modular arithmetic would be a better use of your time (and quicker). $\endgroup$ – user378947 Dec 12 '16 at 3:58
  • $\begingroup$ And how there are 18 ways $\endgroup$ – user123733 Dec 12 '16 at 4:02
  • $\begingroup$ (0,0),(1,9),(4,6)(5,5) $\endgroup$ – user123733 Dec 12 '16 at 4:03
  • 1
    $\begingroup$ Fantastic, thanks. $\endgroup$ – chx Dec 12 '16 at 21:18
18
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please provide me the calculation $\endgroup$ – user123733 Dec 12 '16 at 3:54
  • $\begingroup$ @EricTowers I misread as "integers". I will edit accordingly. $\endgroup$ – mathguy Dec 12 '16 at 15:01
  • $\begingroup$ While solving with a specific N, you can cut some corners by estimating the probability instead - assuming that any number from 10k to N does / does not produce 10-divisible number in the end eventually for upper / lower bounds. These bounds would converge with N going to infinity. For this particular task benefit is negligible, if any, but for similar tasks it may be more fruitful. $\endgroup$ – Daerdemandt Dec 12 '16 at 16:52
  • $\begingroup$ @Daerdemandt - that is what I meant about "if you don't fuss about all the details." It seemed to me the original question was about the meaning of the problem, rather than the exact solution once the precise meaning is clarified. Indeed, for $N-1$ divisible by $10$ the problem is easy to solve, and for $p_N$ for $N-1$ between successive multiples of $10$ you can find lower and upper bounds that converge to the same (constant) value found for $N-1$ multiple of $10$. Those are the "details" I had in mind. $\endgroup$ – mathguy Dec 12 '16 at 17:12
9
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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} $

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But there are infinite numbers . How can we find sample space $\endgroup$ – user123733 Dec 12 '16 at 3:02
  • $\begingroup$ Can you please solve it for me $\endgroup$ – user123733 Dec 12 '16 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.