4
$\begingroup$

If two numbers $x$ and $y$ are chosen at random without any replacement(s) from $S=\{{0,1,2,3.....,189}\}$, then what is the probability that $x^2+ y^2$ is a perfect square?

I noticed that if $x=0$,then the number is a perfect square for all $y$. Hence 189 perfect squares are there. By trial and error, I could also figure out that $(4,5)$,$(6,8)$ are some other perfect squares. But I could not find out all of them.

$\endgroup$
2
  • 2
    $\begingroup$ Perhaps you should tag "Combinatorics" as well. $\endgroup$
    – JKEG
    Oct 11, 2016 at 1:52
  • $\begingroup$ The chance that neither number is $0$ is $(189/190)^2$ so out of $190^2 $ equally likely outcomes, the number of outcomes in which at least one number is $0, $ is $190^2(1-(189/190)^2)=379.$ $\endgroup$ Oct 16, 2016 at 7:18

4 Answers 4

6
+50
$\begingroup$

A possible way to solve this problem is to use the classical Diophantus formulas for the generation of triples of the form $x^2+y^2=z^2$. As shown below, this method leads to a final probability of $\frac {662}{35910} \approx 1.8 \%$. I checked this result by a direct counting algorithm and got the same value.

According to Diophantus parametrization, triples of the form $x^2+y^2=z^2$ with $x,y,z $ integers can be generated by choosing a pair of integers  $(a,b)$ (with $a>b$) and setting $x=a^2-b^2$, $y=2ab$, so that  $z=a^2+b^2$. In particular, if $a $ and $b $ are coprime and of opposte parity, we get a "primitive" triple (i.e. a triple where $gcd (x,y,z)=1$). Interestingly, all primitive triples can be generated in this way. For example, the pair $(2,1)$ generates $(3,4,5) $, the pair $(3,2)$ generates $(5,12,13) $, and so on. Also, when a primitive triple $(x,y,z) $ is identified, we  can generate infinite other triples by simply multiplying it to an integer $n $, that is to say writing $(nx,ny,nz) $. All  triples where a sum of two squared integers is a perfect square can be generated in this way.

Coming back to our random choice of two integers $x $ and $y $ in the range between $0$ and $189$, we can firstly note that there are $189+189=378$ trivial cases of the form $(0,y) $ or $(x,0) $ - i.e. cases where we pick $0$ in one of the two trials - that satisfy the condition that $x^2+y^2$ is a perfect square.  

Focusing on the cases where  $x $ and $y $ are both different from zero, we can count the number of cases where $x^2+y^2$ is a perfect square by identifying the Diophantus pairs $(a,b) $ (with $a >b $) that generate primitive triples (i.e. with  $a $ and $b $ coprime and of opposte parity) and that satisfy the inequalities $x=a^2-b^2 \leq 189$ and $y=2ab \leq 189$. Then, we have to count - for each of these primitive triples - how many triples of the form $(nx,ny,nz) $ satisfy the same inequalities. Noting that the curves $a^2-b^2 = 189$ and $2ab =189$ cross at $a=\sqrt{189 (1+\sqrt{2})/2} \approx 15.1  $, we get that the maximal theoretical value of $a $ is $15$ (for higher integer values, at least one inequality is not satisfied). We can also observe that, for $a=15$, the only value of $b $ that satisfies the inequalities is $b=6$, but since the pair $(15,6) $ violates the assumption that  $a $ and $b $ must be coprime, we can restrict our analysis to the values of $a \leq 14$. In other words, we have to calculate

$$\sum_{a,b} \left \lfloor  \frac {189}{max (2ab,a^2-b^2)}    \right \rfloor$$

where $max $ indicates the higher between the two quantities representing  $x $ and $y $, and the summation extends over all pairs $(a,b) $ that satisfy the conditions described above, in the range $1 \leq a \leq 14$.

We can now identify these pairs of integers $(a,b) $, and count how many triples are generated from each pair. It is not difficult to show that, for $a \leq 10$,  the two inequalities are satisfied for all values of $b < a$.  So we can include all $b <a $ where the two integers are coprime and of opposite parity. Thus our counting procedure begins as follows:

$$(2,1) \rightarrow \lfloor 189/4 \rfloor=47$$

$$(3,2) \rightarrow \lfloor 189/12 \rfloor=15$$

$$(4,1) \rightarrow \lfloor 189/15 \rfloor=12$$

$$(4,3) \rightarrow \lfloor 189/24 \rfloor=7$$

$$(5,2) \rightarrow \lfloor 189/21 \rfloor=9$$

$$(5,4) \rightarrow \lfloor 189/40 \rfloor=4$$

$$(6,1) \rightarrow \lfloor 189/35 \rfloor=5$$

$$(6,5) \rightarrow \lfloor 189/60 \rfloor=3$$

$$(7,2) \rightarrow \lfloor 189/45 \rfloor=4$$

$$(7,4) \rightarrow \lfloor 189/56 \rfloor=3$$

$$(7,6) \rightarrow \lfloor 189/84 \rfloor=2$$

$$(8,1) \rightarrow \lfloor 189/63 \rfloor=3$$

$$(8,3) \rightarrow \lfloor 189/55 \rfloor=3$$

$$(8,5) \rightarrow \lfloor 189/80 \rfloor=2$$

$$(8,7) \rightarrow \lfloor 189/112 \rfloor=1$$

$$(9,2) \rightarrow \lfloor 189/77 \rfloor=2$$

$$(9,4) \rightarrow \rfloor 189/72 \rfloor=2$$

$$(9,8) \rightarrow \lfloor 189/144 \rfloor=1$$

$$(10,1) \rightarrow   \lfloor 189/99 \rfloor =1$$

$$(10,3) \rightarrow \lfloor 189/91 \rfloor=2$$

$$(10,7) \rightarrow \lfloor 189/140 \rfloor = 1$$

$$(10,9) \rightarrow  \lfloor 189/180 \rfloor =   1$$

For $a=11$ to $15$ some pairs $(a,b)$ with $a $, $b $ coprime and of opposite parity must be rejected because do not satisfy the two inequalities (for example, $(11,10) $, which gives $2ab=220 >189$). Then, continuing our counting with the same procedure, we get: 

$$(11,2) \rightarrow 1$$

$$(11,4) \rightarrow 1$$

$$(11,6) \rightarrow 1$$

$$(11,8) \rightarrow 1$$

$$(12,1) \rightarrow 1$$

$$(12,5) \rightarrow 1$$

$$(12,7) \rightarrow 1$$

$$(13,2) \rightarrow 1$$

$$(13,4) \rightarrow 1$$

$$(13,6) \rightarrow 1$$

$$(14,3) \rightarrow 1$$

$$(14,5) \rightarrow 1$$

The total count, summing the numbers above, is $142$. This expresses the number of valid triples $x^2+y^2=z^2$ where $x $ is odd and  $y $ is even and both are different from zero. Due to the symmetry of the problem, we have to count other $142$ triples where $x $ and $y $ are switched (e.g., $(3,4,5)$ and $(4,3,5) $). This gives a total of $284$ valid triples where $x $ and $y $ are different from zero.

 Adding to these the $378$ triples where $x $ or $y $ is zero, we get a total number of $284+378=662$ valid triples that satisfy the conditions given by the OP. This corresponds to the number of choices of two random numbers $x $ and $y $ in the range from $0$ to $189$, so that $x^2+y^2$ is a perfect square.

Because the total possible choices of $x $ and $y $, if picked without replacement, are $190 \cdot 189=35910$, we conclude that the probability that $x^2+y^2$ is a perfect square is $662/35910 \approx 1.8 \%$.

$\endgroup$
1
  • $\begingroup$ And that 1.8% is big enough to cause the answer to the Boolean Pythagorean triples problem to be NEGATIVE. $\endgroup$
    – user584285
    Jul 18, 2020 at 20:46
5
$\begingroup$

A fundamental Pythagorean triplet $(x,y,z)$ has $\gcd (x,y)=1.$ Every Pythagorean triplet is of the form $(kx,ky,kz)$ where $(x,y,z)$ is fundamental and $k \in \mathbb N.$ When $(x,y,z)$ is fundamental then $$\bullet \;\{x,y\}=\{2mn, m^2-n^2\}$$ where $m,n$ are co-prime members of $\mathbb N,$ with $m>n$ and with exactly one of $m,n$ odd and the other one even.

If we can find all fundamental triplets $(x,y,z)$ with $\max (x,y)\leq 189,$ then then for each one, the non-fundamental triplets in the required range are of the form $(kx,ky,kz)$ for $2\leq k$ and $189\geq k\cdot \max (x,y).$

To find fundamental triplets with $\max (x,y)\leq 189$ : Referring to $\bullet $, consider that $2mn\leq 189\implies mn\leq 94.$ Now $n^2+n=n(n+1)\leq nm\leq 94$ so $$n\leq 9.$$ But we also require $m^2-n^2\leq 189.$ So $m^2-9^2\leq m^2-n^2\leq 189,$ implying $m\leq 270. $ Hence $$m\leq 16.$$ Altogether we have now $n<m\leq 16$ with $n\leq 9,$ with $\gcd (m,n)=1,$ and with $m$ odd and $n$ even, OR $m$ even and $n$ odd. Thus the values of $m,n$ are among the following: $$m\in \{10,12,14,16\}, n\in \{1,3,5,7,9\}.$$ $$ m=8,n\in \{1,3,5,7\}.$$ $$ m=6, n\in \{1,5\}.$$ $$ m=4, n\in \{1,3\}.$$ $$m=2,n=1.$$ $$ m\in \{9,11,13,15\}, n\in \{2,4,6,8\}.$$ $$ m=7, n\in \{2,4,6\}.$$ $$ m=5, n\in \{2,4\}.$$ $$ m=3,n=2.$$ Not all of the above pairs will give fundamental triplets in the required range. Some of them give $m^2-n^2>189$ or $2mn>189,$ and some of them are (e.g. $m=14,n=7$) are not co-prime pairs. So some of the above pairs must be removed. This is a matter of some elementary arithmetic. (In particular all the cases with $m=16$ are to be removed, for if $n\leq 7$ then $ 16^2-n^2>189,$ and if $n=9$ then $2mn=2\cdot 16\cdot 9>189.$)

$\endgroup$
1
  • $\begingroup$ I considered that with a cap of 189, trial and error on paper would work, but I thought that if the cap was, say, 10 million, you'd want a better method. $\endgroup$ Oct 18, 2016 at 3:17
4
$\begingroup$

Hey I'm no number theorist, but I'm pretty sure you are looking for solutions to the equation

$x^2 + y^2 = z^2$. Look familiar? You need Pythagorean triplets such that $x,y \leq 189$.

Hope this can get you started.

$\endgroup$
4
  • $\begingroup$ Absolutely true. And while you may not be a number theorist, this is precisely the answer simplest for the OP. Of course, studying the methods used to generate the triples is fascinating.... I believe you can do it with a generalization of the solution to Pells Equation? Correct me if I'm wrong here, I'm no number theorist myself, but I dabble ;) $\endgroup$ Oct 11, 2016 at 2:07
  • $\begingroup$ You can generate all primitive Pythagorean triples with a very simple process. It's not just trial and error. $\endgroup$ Oct 11, 2016 at 2:13
  • $\begingroup$ @Deepak I get that. But typically, I try not to do too much for the questioner if he/she hasn't started the problem. $\endgroup$ Oct 11, 2016 at 2:20
  • $\begingroup$ The set S is quite small, so couldn't you code a simple algorithm to count the number of feasible pairs, or do you need a more general solution? $\endgroup$
    – K. Miller
    Oct 11, 2016 at 2:57
1
$\begingroup$

Hint: You can use this, Pythagorean triples are in the form of:

$$(m^2-n^2, 2mn, m^2+n^2)$$

Given $m>n$.

Hope you can take it form here. Its basic combinatorics with a little bit of logic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .