Let $S$ be a set of integers ${1,2,....,n}$ $2$ numbers a and b are selected from $S$.
(Let's solve them both with and without replacement, for a complete reference to someone with the same question In Future)
(I was trying for with replacement)
Find the probability that $a+b$ is a perfect square that also belongs to $S$ (i.e., $a$,$b$,$a+b$ belong to $S$).
My approach
We basically need to solve $root n$ equations as we can have $root n$ possible perfect square from $1....n$
(Using the solution of the equation of two variables adding to a number from permutation, combinations.. and summing them all and then division by $n*n$ to calculate the probability)
But somehow I am lost while calculating the summation..
Also I observed that the solutions to some trivial values too $n$=$4$ it's 2
$n$=$9$ it's 8
Then it's 15, then it's 24 etc..
(Basically from some trivial n it seems like it's equivalent to the square -1 but it's not true as there are some repetions too, as a's and b 's order won't matter)
Can someone help me with my way or if there exists a better way to solve it, please share..
Thanks..
Ok I got it it's the summation of 3,8,15,24 till √n -1(for replacement case)
I would think of the following questions:
a) What is the probability that a+b=k for some k? (This is essentially a counting argument, how many pairs (a,b) sum up to k? (for instance, for 7, there are 6 pairs (1,6), (2,5), (3,4), (4,3), (2,5), (6,1)).
b) $\mathbb{P}$($k$ is a perfect square) = $\mathbb{P}(k = 1 \cup k = 4 \cup ... k = \lfloor{\sqrt{n}\rfloor}^2 )$, now what can you say about these events? (It might be easier to think of two cases if you only care about asymptotics: $n$ being a perfect square, and $n$ being one less than a perfect square)