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
    $\begingroup$ Perhaps you should tag "Combinatorics" as well. $\endgroup$ – JKEG Oct 11 '16 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$ – DanielWainfleet Oct 16 '16 at 7:18
7
+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$
  • $\begingroup$ And that 1.8% is big enough to cause the answer to the Boolean Pythagorean triples problem to be NEGATIVE. $\endgroup$ – EulerSpoiler Jul 18 '20 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$
  • $\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$ – DanielWainfleet Oct 18 '16 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$
  • $\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$ – Brevan Ellefsen Oct 11 '16 at 2:07
  • $\begingroup$ You can generate all primitive Pythagorean triples with a very simple process. It's not just trial and error. $\endgroup$ – Trevor Squires Oct 11 '16 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$ – Trevor Squires Oct 11 '16 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 '16 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$

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.