Thread: How do I prove this?

Of the following three numbers:

65^1000 - 8^2001 + 3^177

79^1212 - 9^2399 + 2^2001

24^4493 - 5^8192 + 7^1777

Show that the product of two of these is nonnegative. The book says it is unnecessary to evaluate any of these numbers.

If you think about it in a more abstract way, you will see that the following must be true:

Let a,b and c be 3 real numbers. Then the product of 2 of those must be non-negative.

Note that some products of other couple of these numbers don't necessarily have to adhere to this. The statement is that there exists one such pair among the 3. Can you think of a way to prove it? What are you options?

Oh, man. I didn't realize how easy this problem was. Its just simple logic. So there are eight possiblities.
i. If a≥0, b≥0 and c≥0
Then the product of any two of these numbers will be nonnegative.

ii. If a≥0, b≥0, c<0

Then ab≥0

iii. If a≥0, b<0, c≥0

Then ac≥0

iv. If a≥0, b<0, c<0
Then bc≥0

v. a<0, b≥0, c≤0
So, bc≥0

vi. a<0, b≥0, c<0
So, ac≥0

vii. a<0, b<0, c≥0
So, ab≥0

viii. a<0, b<0, c<0
Then the product of any pair will be nonnegative.

Precisely! Since it was so easy, can you generalize to bigger sets? Let [LaTeX ERROR: Convert failed] . Let [LaTeX ERROR: Convert failed] be a product of k integers from the set. Let N(n) be the maximum k such that [LaTeX ERROR: Convert failed] is non-negative. You just showed that N(3) = 2. What is N(4), N(5)? What about in general?

It can help you to think of things this way: your cases 1), 2) and 5) are identical since you have 2 non-negative integers and 1 negative. This can be represented by the sequence (+,+,-).

The possible cases for 3 integers are:

+++
++ -
+ - -
- - -

In general, for n integers, you have n+1 cases since you can have 0 negative numbers, 1 neg. num., 2, 3,.. all the way up to n. The number of those is n+1.

If n=4, N(n)=2
(++)++
(++)+-
(++)--
+-(--)
----

If n=5, N(n)=4
(++++)+
(++++)-
+(++--)
(++--)-
+(----)
-(----)

If n=6, N(n)=4
(++++)++
(++++)+-
(++++)--
+(++--)-
(++--)--
+-(----)
(----)--

If n=7, N(n)=6
(++++++)+
(++++++)-
+(++++--)
(++++--)-
+(++----)
(++----)-
+(------)
-(------)

What I'm noticing is that for every next odd integer, N(n) goes up by 2, but on the even integers, it stays the same as the previous odd integer. So, N(4)=2, N(5)=4, N(6)=4, N(7)=6, etc. So, I conjecture that for every positive integer n with n≥2, if n is odd, then N(n)=n-1, and if n is even, then N(n)=n-2. Is there a way to prove this?

How is this as a start?

If the number of negative integers in a product is odd, then the product is negative. Therefore, the maximum k such that Pk is nonnegative has to be even, to avoid the possibility that there is an odd number of negative integers in the product. N(n)≠n because the number of possibilities where the number of negative integers in the product of all integers in the set is negative is always greater than 0 (specifically, the number of possibilities where the number of negative integers is odd is n/2 if n is even, and (n+1)/2 if n is odd). When n is odd, n-1 is even. When n is even, n-2 is even.

I know this isn't a proof, and is pretty sloppy. Does anybody have any ideas to improve it?

I actually think that's pretty good there.

When you are proving a maximum you need to do two things:

- Show that the statement is true for some integer.
- Show that the statement is not true for any bigger integer

You seem to have done both of those things. However, you need a bit more rigor to make it a tight proof.