Any 25 different positive numbers property...

A

apple2357

Full Member
Joined
Mar 9, 2018
Messages
540
Take any 25 different positive numbers. I am trying to prove that you can choose two of them such that none of the other numbers equals either their sum or their difference. This is how far i have got so far:

Suppose you took 25 odd numbers, i can pick any two odd numbers ( say 7 and 11), if i find the difference (11-7) which is 4, thats not in the list, if i find the sum (11+7) which is 18 that is also not in the list. This is because the sum and difference of two odd numbers is always even. So the result hold if the numbers are odd.
But for any 25 numbers? Clearly i can pick the last two numbers in the list, the sum will always be outside the list, but i can't say in general about the difference?
Does odd/even reasoning help here? I wondered if i need to use some kind of inductive argument but i can't think clearly.

Any thoughts/hints/ ideas to explore ?
 
I am lost by this question. Pick two distinct integers a and b such that

[MATH]a > 2b > b > 0 \implies a + b > a > 0 \text { and } a - b > b > 0.[/MATH]
I can keep replicating that forever.

So what you are trying to prove is false.
 
apple2357 said:
Take any 25 different positive numbers. I am trying to prove that you can choose two of them such that none of the other numbers equals either their sum or their difference. This is how far i have got so far: Does odd/even reasoning help here? I wondered if i need to use some kind of inductive argument but i can't think clearly. Any thoughts/hints/ ideas to explore ?
Click to expand...
There \(\dbinom{25}{2}=300\) ways to choose two from twenty-five. From The odd even connection is indeed very useful to explore. Do you know about the pigeonhole principle ? Of three hundred pairs how many different sums and/or differences are there?
 
Last edited:
pka said:
There \(\dbinom{25}{2}=300\) ways to choose two from twenty-five. From The odd even connection is indeed very useful to explore. Do you know about the pigeonhole principle ? Of three hundred pairs how many different sums and/or differences are there?
Click to expand...
I will look up the pigeonhole principle!
 
I fear I may have misunderstood the question. Given a set of 25 positive INTEGERS, is it necessarily true that there exists at least one pair of them such that their sum does not equal any of the other integers in the set or that their difference does not equal any of the other integers in the set? Is that the question?

I suspect that I answered the question of whether there are circumstances where it can be true. Obviously it can be true. Consider the set

[MATH]\{10^0, \ 10^1, 10^2, \ ..., \ 10^{23}, \ 10^{24}.[/MATH]
No sum is a power of 10, and neither is any difference.

If I misunderstood the question, I apologize.
 
Thanks for clarifying the wording. I was a bit unclear.
I like your example, i used odd numbers to illustrate the point. The proof is about any 25 positive integers...
 
OK When I am not playing the NANDgame (I am working on the ALU right now) or doing something actually productive, I’ll be thinking about your problem

We. have a set of n distinct positive integers. Suppose that n is any integer > 2. The set of n distinct integers will contain a largest integer.

The sum of that largest integer and any other integer in the set is obviously not in the set. There are n - 1 differences between the largest integer as minuend and the other integers as subtrahends. Either at least one of those differences is in the set, or none is in the set. In the latter case, there at least n - 1 pairs such that their sums and differences are BOTH not in the set. And we have succeeded.

But there is nothing to prevent one or more of those differences from being in the set because the set may contain any distinct integers. If that is the case, then consider the set that excludes the largest integer, but includes all the other integers.

Now repeat the process on the new set.

We either will find a pair that meets our criterion before we get a set containing only 2 integers or not. If we do find such a pair before we reduce the set to 2 integers, then we have succeeded. If, however, we reduce to 2 positive integers, their sum is clearly larger than either, but their difference will be in the set if the larger is twice the smaller.

Thus, IF MY LOGIC IS CORRECT, the proposition is not necessarily true.
 
I must admit every time i think i have got my head around what the problem is actually asking then i overthink it an get confused.

I tried simplifying the problem, let's think of sets of size 2?

I claim there are no sets of size 2 in which its elements are all positive integers and it has the property that for every pair of distinct elements of the set, either their sum or their difference is a distinct third element of the set.

There are sets of size 3.. e.g. (1,3,4) or (7,11,18)

We are trying to prove there are no sets of size 25.

I think thats right.
 
apple2357 said:
I must admit every time i think i have got my head around what the problem is actually asking then i overthink it an get confused.

I tried simplifying the problem, let's think of sets of size 2?

I claim there are no sets of size 2 in which its elements are all positive integers and it has the property that for every pair of distinct elements of the set, either their sum or their difference is a distinct third element of the set.

There are sets of size 3.. e.g. (1,3,4) or (7,11,18)

We are trying to prove there are no sets of size 25.

I think thats right.
Click to expand...
I don't care how big n is. If the set includes a, 2a, and 3a, then a + 2a is in the set and 3a - 2a is in the set as is 2a - a.

A set of 2 does have the attribute you want. But I can construct a set of 3 that does not have that attribute. So there are some finite sets of numbers where the proposition is false.

EDIT: Either my mind is scrambled from playing NAND, or what you are trying to prove is false. In the first case, I obviously cannot be much help.
 
apple2357 said:
Take any 25 different positive numbers. I am trying to prove that you can choose two of them such that none of the other numbers equals either their sum or their difference.
Click to expand...
Can we exam this item at a time.
  1. Given any set of twenty-five positive integers
  2. we can select two of those say \(a~\&~b\) such that
  3. no number in the set equals \(|a+b|\text{ nor }|a-b|\)
It seems to me that the above is the meaning of the question. Is it?
 
pka said:
Can we exam this item at a time.
  1. Given any set of twenty-five positive integers
  2. we can select two of those say \(a~\&~b\) such that
  3. no number in the set equals \(|a+b|\text{ nor }|a-b|\)
It seems to me that the above is the meaning of the question. Is it?
Click to expand...
I'd agree with that.
 
Ok, I am going to have another go at explaining what I think the question is really claiming...

So for example,

Let the set be (1, 2, 3, …., 24, 25). For each pair of numbers in this set either the sum or the difference (or both) is a member of the set. So, for example, if we select 5 and 17 both the sum 22 and the difference 12 are in the set. Now choose 18 and 19. In this case only the difference is in the set.
But does it work for every such pair? The questions claims that there is always at least one pair of numbers for which it doesn't work.

In this case 12, 24 doesn't work. 36 is not in the set and the difference, 12, is not 'one of the other numbers'

So we have to prove we can get a pair like this in ANY 25 numbers.
 
apple2357 said:
Ok, I am going to have another go at explaining what I think the question is really claiming...

So for example,

Let the set be (1, 2, 3, …., 24, 25). For each pair of numbers in this set either the sum or the difference (or both) is a member of the set. So, for example, if we select 5 and 17 both the sum 22 and the difference 12 are in the set. Now choose 18 and 19. In this case only the difference is in the set.
But does it work for every such pair? The questions claims that there is always at least one pair of numbers for which it doesn't work.

In this case 12, 24 doesn't work. 36 is not in the set and the difference, 12, is not 'one of the other numbers'

So we have to prove we can get a pair like this in ANY 25 numbers.
Click to expand...
The problem for me is that it is not clear what the "it" represents in "there is always at least one pair of numbers for which it doesn't work."

If "it' here means "a pair of distinct elements for which the absolute value of their difference is in the set OR for which their sum is in the set," then I claim that the proposition is false and so cannot be proved. Here is a counter-example.

Consider the set of positive integers {a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a, 11a, 12a, 13a, 14a, 15a, 16a, 17a, 18a, 19a, 20a, 21a, 22a, 23a, 24a, 25a}.

Now choose b from the set and c from the set such that b and c are not the same.

Then there exists integer p such that b = ap and 0 < p < 26 and
there exists integer q such that p and q are not =, c = aq, and 0 < q < 26

[MATH]0 < q < 26 \implies 1\le q \le 25 \implies - 25a \le - aq \le - a.[/MATH]
[MATH]0 < p < 26 \implies a \le ap \le 25a.[/MATH]
[MATH]\therefore a < b - c \le 24a \ \because \ b \ne c.[/MATH]
And obviously b - c is a multiple of a. Thus, there is at least one set of 25 positive integers such that the absolute value of the difference between any two distinct members is a member of the set.

But if "it' means "a pair of distinct elements for which the absolute value of their difference is in the set AND for which their sum is in the set," then I claim that the proposition is true but trivial because the sum of any element of the set and the largest element in the set is outside the set so there are at least n - 1 pairs that fail.

Back to NAND.
 
You must log in or register to reply here.
Top