Finding pairs of numbers that meet a specific criteria

[musicgold]

Hi,

I am struggling with this strange problem.

I have to find pairs of positive integers that satisfy two specific conditions.

1. you can’t go from one pair to another by subtracting/adding the same number to both members of the pair.

2. You can’t go from one pair to another by subtracting/adding a number from one of the numbers in the pair.

I have so far found the following pairs using a graph paper. Note that the order of the numbers in a pair is not important.

(0,0) (1,2) (3, 5) (4, 7) (6, 10) (8, 13)

I want to able to find say 100th pair. How should I go about doing this?

Also, what branch of mathematics handles this kind of problems?

Thanks.

 

[gsal]

I would simply find the pairs in a brute-force manner by writing a simple program in the language of your preference.

Is there any other condition for the pairs? Can you start from (3,194) for example, and start incrementing 3 and reducing 394? why do you seem to just be going up on both numbers?

 

[musicgold]

Thanks gsal.

I did think about using the brute-force method, but before that I wanted to see if there was a more elegant solution.

Is there any other condition for the pairs? Can you start from (3,194) for example, and start incrementing 3 and reducing 394? why do you seem to just be going up on both numbers?

No there is no other explicit condition. However given the inherent structure ( every pair takes into account the pairs lower than it), I don't think you can start from (3, 194). I started from (0,0) because I felt it was an easy boundary given that we are not working with -ve integers.

Thanks.


Question cross posted at: http://mathforum.org/kb/thread.jspa?threadID=2310301

 

[gsal]

The reason why I thought of starting with a pair where the two numbers are far apart and then simply increment one and reduce the other one is because this would intrinsically let you not have to worry about condition 1...am I correct?

 

[musicgold]

gsal,

Sorry, I don't understand your logic.:grumpy:

 

[dlh]

It looks a bit like the n-queens problem, to me.

Definition of the n-queens problem:
Place n queens on an n*n chessboard so that no queen is on the same diagonal or in the same row or column as any other queen.

The coordinate pts (x, y) you are choosing could represent a queen at the position (x, y) on a 100*100 chessboard.

Adding/subtracting a number from both members of a pair is the same as moving the pair along a diagonal;
and adding/subtracting a number from one member of a pair is the same as moving along a row or column.

http://www.math.utah.edu/~alfeld/queens/queens.html

 

[gsal]

I was thinking that I might be able to break down condition 1 into two statements, like:

1.a you can’t go from one pair to another by subtracting the same number to both members of the pair.

1.b you can’t go from one pair to another by adding the same number to both members of the pair.

But after reading dlh's post, which sounds like it is totally related, I realize that condition 1 may also include:

1. you can’t go from one pair to another by subtracting a number from of the members of the pair and adding the same number to the other one.

Doing the latter would place the new pair on the same diagonal...diagonal from upper-right to lower-left...

 

[musicgold]

Thanks gsal.

dlh,

Yes, that is a similar problem. Thanks a lot. Is there any other way, other than the brute-force, to solve such a problem?

 

[dlh]

musicgold, the usual way to solve it is to write a recursive program.

 

[gsal]

I don't see this problem as being one to be solved with recursion...but I just may not see it.

 

[Trisha07]

Thanks!

 

[willem2]

I have so far found the following pairs using a graph paper. Note that the order of the numbers in a pair is not important.

(0,0) (1,2) (3, 5) (4, 7) (6, 10) (8, 13)

I want to able to find say 100th pair. How should I go about doing this?

Also, what branch of mathematics handles this kind of problems?

Thanks.

Of course, there's more than one way to define the 100th pair.

However, if you start with (0,0), and then always take the lowest first number that's still available and then the lowest second number that's still available, it seem that the n-th pair
is:

$$(\lfloor \phi n \rfloor, \lfloor (\phi+1) n \rfloor)$$

where $\phi$ is the golden ratio or $\frac {1}{2} + \frac {\sqrt{5}}{2}$ or 1.618034...

and $\lfloor x \rfloor$ is x rounded down to the nearest integer.

This sequence (the first number of the pairs) appears in the Online encyclopedia of integer sequences, http://oeis.org/A066096 but I didn't see this application.

Still working on a proof by induction. It's correct up to n=100.