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

Home > Just Math
Sets' intersection (Posted on 2017-02-16) Difficulty: 3 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information