wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> How many values?
        
(Message started by: pcbouhid on Nov 26^th, 2005, 5:23am)

Title: How many values?
Post by pcbouhid on Nov 26^th, 2005, 5:23am

Each number x(n) may be [sqrt(2) - 1] or [sqrt(2) + 1.]

How many different integer values might be the sum S:

S = x(1)*x(2) + x(2)*x(3) + x(3)*x(4) +...+ x(2003)*x(2004)?

Title: Re: How many values?
Post by BNC on Nov 26^th, 2005, 6:09am

The way I see it, [hide] if we'll call one value a and the other b, ab will give an integer result, as will a^2+b^2 (a^2, and b^2 alone won't).
Hence, we need an equal number of "a strings" (repeated values of a's, that will give a^2's) and "b strings". The location and distribution of these strings does not matter.

The question then becomes: how many such (#a-strings = #b-strings) combinations exist?

There can be any number between 0 (for any n, x(n)!=x(n+1) and 1001 (one value change).

The answer, then, would be 1002.
[/hide]

Title: Re: How many values?
Post by pcbouhid on Nov 26^th, 2005, 6:20am

Not quite.

Title: Re: How many values?
Post by rmsgrey on Nov 26^th, 2005, 6:20am

[hide]503506[/hide]

Assuming my arithmetic was up to the task.

Justification:

[hideb]Each of the 1002 terms of the sum can be 3-2[sqrt]2, 1 or 3+2[sqrt]2. Call them x, y and z. For ax+by+cz=dx+ey+fz to hold, c-a=f-d must also hold (to have the same number of [sqrt]2's) as must 3a+b+3c=3d+e+3f (to equate rational parts) and a+b+c=d+e+f=1002. So a+c=d+f so a=d, c=f, and b=e must hold.

So any three values 0<=a,b,c<=1002 with a+b+c=1002 will give a unique value for S. There are 503506 such triples (¹⁰⁰⁴C₂)[/hideb]

Title: Re: How many values?
Post by pcbouhid on Nov 26^th, 2005, 6:23am

nope!

Title: Re: How many values?
Post by rmsgrey on Nov 26^th, 2005, 6:54am

OK, yeah, integer values...

[hide]502[/hide]

Because:
[hideb]Continuing from my previous analysis, using the same notation: for integer S, a=c must hold, so 2a+b=1002, so 0<=a<=501, for 502 possibilities[/hideb]

Title: Re: How many values?
Post by BNC on Nov 26^th, 2005, 7:32am

rmsgrey,

There are 2003 terms in the sum, not 1002.

OK, I see the problem:
[hide]
(sqrt(2)-1)^2+(sqrt(2)+1)^2 = 6 = 6*[(sqrt(2)-1]*[sqrt(2)+1]
So some of the 1002 values overlap.
[/hide]
I don't see the solution still, though...

Title: Re: How many values?
Post by pcbouhid on Nov 26^th, 2005, 8:07am

rmsgrey´s last answer is [hide]right[/hide].

Title: Re: How many values?
Post by BNC on Nov 26^th, 2005, 8:10am

on 11/26/05 at 08:07:27, pcbouhid wrote:

rmsgrey´s last answer is [hide]right[/hide].

The reasoning or the result (or both)?

Title: Re: How many values?
Post by pcbouhid on Nov 26^th, 2005, 8:35am

Thw answer, certainly. His reasoning is a little bit confusing when he introduces x, y, and z, and extracts some equalities.

If you excuse me, I´ll take a look more closely latter.

Title: Re: How many values?
Post by Barukh on Nov 27^th, 2005, 12:27am

I really cannot see a flaw in BNC's reasoning...

What would be the answer if instead of 2004 the last index is 6? I get 3 different sums then:

ab + ba + ab + ba + ab = 5
aa + ab + bb + ba + ab = 9
aa + aa + ab + bb + bb = 13

:-/

Title: Re: How many values?
Post by rmsgrey on Nov 27^th, 2005, 8:47am

on 11/26/05 at 07:32:26, BNC wrote:

rmsgrey,

There are 2003 terms in the sum, not 1002.

Good point.

I think I'll quit while I'm ahead - on current form, I'll probably just come up with the answer "42" next time...

Title: Re: How many values?
Post by rmsgrey on Nov 27^th, 2005, 9:03am

on 11/26/05 at 07:32:26, BNC wrote:

OK, I see the problem:
[hide]
(sqrt(2)-1)^2+(sqrt(2)+1)^2 = 6 = 6*[(sqrt(2)-1]*[sqrt(2)+1]
So some of the 1002 values overlap.
[/hide]

A fair chunk of my first post went to proving that that isn't a problem - replacing 2 terms with 6 changes the total number of terms, so you don't get overlap after all.

Despite what I just said, I have had another shot at the problem, and got an answer of [hide]1002[/hide] this time - [hideb]Since the values for S each have a unique set {a, b, c} for the number of times each term appears, any two instances of the same sum must be rearrangements of the terms of each other. So you only need to consider sums where the first c terms are x, followed by a single y, then c z's with the remaining terms y (x...xyz...zy...) (in BNC's analysis, aa=x, bb=z, and y is either ab or ba)

So 0<=c<=2003/2 so can take 1002 possible values.[/hideb]

In other words, I now agree with BNC

Title: Re: How many values?
Post by pcbouhid on Nov 27^th, 2005, 1:35pm

nope!

Title: Re: How many values?
Post by Eigenray on Nov 27^th, 2005, 7:15pm

I have to agree with BNC, rmsgrey, and Barukh . . . it's definitely [hide]1002[/hide]:

[hideb]Of the 2003 terms in the sum, X of them are aa, another X of them are bb, and 2003-2X of them are either ab or ba. Then
S = 2003 + 4X,
and 0 <= X <= 1001, so there are no more than 1002 possibilities. On the other hand, we can take (X+1) a's, then (X+1) b's, following by alternating a's and b's, so all 1002 possibilities are realized:
S = 2003, 2007, 2011, ..., 6007.[/hideb]

Title: Re: How many values?
Post by SMQ on Nov 27^th, 2005, 8:45pm

on 11/27/05 at 13:35:24, pcbouhid wrote:

nope!

Hmm, you state that with confidence, yet four of the best mathematical minds on this forum appear to disagree with you and agree with one another...this should be interesting. ;D

For what it's worth, BNC, rmsgrey, Barukh and Eigenray are demonstrably right. Consider the following C++ program based on Eigenray's description:

Code:

#include <iostream>
#include <cmath>
using namespace std;
int main() {
for (int X = 0; X < 1002; ++X) {

double x[2005];
for(int i = 1; i <= 2004; ++i) {
if (i <= X + 1) x[i] = sqrt(2.0) - 1.0;
else if (i <= X * 2 + 2) x[i] = sqrt(2.0) + 1.0;
else if (i % 2 == 1) x[i] = sqrt(2.0) - 1.0;
else x[i] = sqrt(2.0) + 1.0;
}

double S = 0;
for(int j = 1; j <= 2003; ++j) {
S += x[j] * x[j+1];
}

if (X > 0) cout << ", ";
if (X % 10 == 0) cout << endl;
cout << S;
}

cout << endl;
return 0;
}

The outer loop iterates over the 1002 proposed solutions. The first inner loop generates an array of x[1..2004] which clearly meets the problem statement as each element is set to either sqrt(2)-1 or sqrt(2)+1. The second inner loop sums the terms, again, clearly according to the prblem statement. When run this program outputs 1002 distinct integer results: 2003, 2007, ..., 6007, so there are demonstrably at least 1002 unique integer sums.

--SMQ

Title: Re: How many values?
Post by pcbouhid on Nov 28^th, 2005, 11:44am

As I already said to Icarus, I´m here to learn with you.

Please, tell me what´s wrong with this solution:

[hide]The possible products are:

(sqrt(2) - 1) * (sqrt(2) - 1) = 3 - 2*sqrt(2)

(sqrt(2) + 1) * (sqrt(2) + 1) = 3 + 2*sqrt(2)

(sqrt(2) + 1) * (sqrt(2) - 1) = 1.

Suppose we have A products of the first form, B products of the second, and (1002 - A - B) products equal to 1.

The sum will be A * (3 - 2*sqrt(2)) + B * (3 + 2*sqrt(2)) + (1002 - A - B) * 1 = 1002 + 2 * (A + B) + 2 * (B - A) * (sqrt(2)).

To the sum be an integer value we must have B = A, thus the sum is equal to (1002 + 4*A).

Since A vary from 0 to 501 (because A+B can´t be greater than 1002), the sum can result in 502 different integer values[/hide].

Title: Re: How many values?
Post by SMQ on Nov 28^th, 2005, 12:39pm

No worries--we're all here to learn!

It looks like you made a simple mistake, either in stating the problem or in your soultion; as BNC stated above:

on 11/26/05 at 07:32:26, BNC wrote:

There are 2003 terms in the sum, not 1002.

If, rather than S = f(1)*f(2) + f(2)*f(3) + ... + f(2003)*f(2004) as stated, S were to = f(1)*f(2) + f(3)*f(4) + ... + f(2003)*f(2004) your solution would indeed be accurate.

Hope that clears up all our counfusion! :)

--SMQ

Title: Re: How many values?
Post by pcbouhid on Nov 28^th, 2005, 2:19pm

All I have to do is apologize for my mistake and sorry for the time you wasted. I was only "watching" yours answers, since I already knew "my answer".

Indeed, my problem is wrong and the correct one is f(1)*f(2) + f(3)*f(4) + ...

Hope you forgive me.

Title: Re: How many values?
Post by BNC on Nov 28^th, 2005, 2:45pm

on 11/28/05 at 14:19:36, pcbouhid wrote:

Hope you forgive me.

Nothing to forgive... we all make mistakes.

I would like to take the chance to thank you for the many new puzzles you posted recentlly. This place is now buzzing with activity!

Title: Re: How many values?
Post by pcbouhid on Nov 28^th, 2005, 3:26pm

Should I remove this problem?

And tk you for your words.

Title: Re: How many values?
Post by BNC on Nov 28^th, 2005, 3:50pm

on 11/28/05 at 15:26:33, pcbouhid wrote:

Should I remove this problem?

Not at all. In fact, I, personally, like the version you posted by mistake better!