All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Sets' intersection (Posted on 2017-02-16)
Let k be a positive integer.
Prove that there must exist a positive integer n such that the sets
A( A={1^2, 2^2, 3^2, . . . }) and B ( B = {1^2+n, 2^2+n, 3^2+n, . . . }) share exactly k identical members.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 2
One way to restate this problem is to say that it is possible to choose a positive integer n such that the equation:

a^2 = b^2 + n (a, b also positive integers) has exactly k solutions, regardless of choice of k > 0

Rewriting,

n = a^2 - b^2 = (a+b)(a-b)

Since b > 0, these two factors must be distinct (if a+b = a-b then b must = 0)

Since a and b are integers, these two factors must have the same parity, either both odd or both even. (if one were odd and the other even then their sum would be odd but (a+b)+(a-b) = 2a which must be even)

So the number of solutions is equal to the number of ways to factor n into two distinct factors that are either both odd or both even.

You can construct an n with any desired number of solutions. For example n = 3*2^(k+1) has exactly k such factorizations: The 3 must belong to one factor, each factor must have at least one 2, and any number in [0,k-1] (k choices) of the remaining 2's can belong to the factor that has the 3. In the case of k = 2, n= 24 is one such desired number. There are exactly 2 solutions to a^2 = b^2 + 24 -- 7^2 = 5^2 + 24 and 5^2 = 1^2 + 24.

Clearly there are an infinite number of n's that server for any k -- any prime > 2 could be substituted in my example for "3" and the logic would still hold. Of course only one such n is required for the existence proof the problem requests.

 Posted by Paul on 2017-02-16 11:34:57

 Search: Search body:
Forums (0)