#105456 - 17/07/2002 09:42
Mathematical Puzzle
[Re: BryanR]
|
old hand
Registered: 30/07/2001
Posts: 1115
Loc: Lochcarron and Edinburgh
|
Okay, here's one for people who are "math guys":
I have a sequence such that
x_1 = 1
and
x_{n+1} = (1 + sum_i=1^n{{x_i}^2}) / n
for n>=1.
So the sequence begins 1, 2, 3, 5, 8, ...
Hypothesis: all x_n are integers.
Puzzle: prove or disprove the hypothesis.
This one has been bugging me on and off for over 10 years, so if someone has a solution, I'll be happy all day.
_________________________
Toby Speight 030103016 (80GB Mk2a, blue) 030102806 (0GB Mk2a, blue)
|
Top
|
|
|
|
#105458 - 17/07/2002 19:08
Re: Puzzle
[Re: ]
|
carpal tunnel
Registered: 08/07/1999
Posts: 5543
Loc: Ajijic, Mexico
|
Yep. Every inch does have to be walked. But with John's method, part of the time they're walking at the same time in different areas, thus walking those inches twice as fast.
Yes.
A very succinct explanation. Well done!
tanstaafl.
_________________________
"There Ain't No Such Thing As A Free Lunch"
|
Top
|
|
|
|
#105459 - 17/07/2002 22:27
Re: Mathematical Puzzle
[Re: tms13]
|
pooh-bah
Registered: 09/09/2000
Posts: 2303
Loc: Richmond, VA
|
so if your sequence is correct, then I think you mean "/ x_n" rather than "/ n". If you mean "/ n" then I think the sequence is 10 not 8, and after about n = 8 or so the numbers just explode upwards -- so much so that I can't even check to see if they really are integers (i wanted to run a few rounds to make sure the hypothesis was right).
However, if you meant "/ x_n" then that's a whole different ballgame... And those provably are integers, and it's actually the fibonacci sequence ... here's why:
define sum(a(b), b, c, d) to be "the sum of a(b) where b goes from c to d" .. to make parsing easier.
i'm switching to definiing n in terms of n-1 rahter than n+1 in terms of n... it made my brain hurt the other way for some reason.
restatement:
x_n = ( 1 + sum( (x_i)^2, i, 1, n-1) ) / x_(n-1)
pull out the last value of the sum:
x_n = ( 1 + sum( (x_i)^2, i, 1, n - 2) + (x_(n-1))^2 ) / x_(n-1)
divide through:
x_n = x_(n-1) + (1 + sum( (x_i)^2, i, 1, n - 2)) / x_(n-1)
the 1 + sum(.., n - 2) by definition is actually x_(n-1)*x_(n-2), which makes it now:
x_n = x_(n-1) + (x_(n-1)*x_(n-2)) / x_(n-1)
simplify and you get:
x_n = x_(n-1) + x_(n-2)
Like I mentioned, though, if you meant "/ n", then I need to go back to the drawing board.
Mike
|
Top
|
|
|
|
#105460 - 17/07/2002 23:41
Re: Mathematical Puzzle
[Re: tms13]
|
pooh-bah
Registered: 09/09/2000
Posts: 2303
Loc: Richmond, VA
|
I hate you for doing this to me ... So I got the "/ n" version down to:
x_n = [ (x_(n-1)) / (n - 1) ] * [ x_(n-1) + n - 2)
if you set x_1=1 and x_2=2 (wonder why it doesn't give you x_2 itself ... weird)
But now I'm kind of stuck ... If (x_(n-1))^2 + (n-2)(x_(n-1)^) somehow can be factored so that there is an (n-1) term in the numerator, that would cancel out the n-1 in the denominator and prove it to be true. But my brain has stopped functioning now that it is 2:30.
You realize you've set jEmplode back an entire day with this question
Mike
|
Top
|
|
|
|
#105461 - 17/07/2002 23:57
Re: Mathematical Puzzle
[Re: mschrag]
|
carpal tunnel
Registered: 20/12/1999
Posts: 31578
Loc: Seattle, WA
|
If you continue to use algebra on the BBS, I will have to hunt you down and kill you. Slowly. With a very dull knife.
|
Top
|
|
|
|
#105462 - 18/07/2002 03:56
Re: Mathematical Puzzle
[Re: mschrag]
|
old hand
Registered: 30/07/2001
Posts: 1115
Loc: Lochcarron and Edinburgh
|
In reply to:
If you mean "/ n" then I think the sequence is 10 not 8, and after about n = 8 or so the numbers just explode upwards -- so much so that I can't even check to see if they really are integers
Yes, I do really mean "/n", and yes, the numbers do get very big very quickly - it doesn't take long to run out of screen space ![](/images/icons/smile.gif) And sorry for the mistake in my mental arithmetic - x_5 is indeed 10.
It's a long time since I've actually looked at this one, but ISTR making some progress by extending the sequence to include x_0 = 1. Then the expression becomes
x_{n+1} = sum_i=0^n{{x_i}^2} / n
and
n.x_{n+1} = (n-1)x_n + {x_n}^2
n (x_{n+1} - x_n} = {x_n}^2 - x_n
= x_n (x_n - 1)
So
x_{n+1} = x_n + x_n(x_n - 1) / n
Which would be great if I could somehow show that x_n or x_n - 1 is a multiple of n ... Unfortunately, it appears to alternate, so that for odd n, x_n is a multiple of n, and for even n, x_n - 1 is a multiple of n.
(Hmm, I'd forgotten how ugly TeX notation can be when you're not used to it)
_________________________
Toby Speight 030103016 (80GB Mk2a, blue) 030102806 (0GB Mk2a, blue)
|
Top
|
|
|
|
#105463 - 18/07/2002 04:23
Re: Mathematical Puzzle
[Re: tfabris]
|
Pooh-Bah
Registered: 21/07/1999
Posts: 1765
Loc: Brisbane, Queensland, Australi...
|
Try a runsable spoon. not as sharp but quite effective.
_________________________
--
Murray
I What part of 'no' don't you understand?
Is it the 'N', or the 'Zero'?
|
Top
|
|
|
|
#105464 - 18/07/2002 07:56
Re: Mathematical Puzzle
[Re: tms13]
|
pooh-bah
Registered: 09/09/2000
Posts: 2303
Loc: Richmond, VA
|
x_{n+1} = x_n + x_n(x_n - 1) / n
I think you have to define x_2 explicitly .. My brain can't comprehend why, but if you use this to find x_2, it returns 1 -- mine did this too (since x_n - 1 = 0 for x_1) ... no idea why.
I wonder since we have two different equations, is it possible to set them equal to eachother and find out anything more interesting.
ms
|
Top
|
|
|
|
#105465 - 18/07/2002 08:00
Re: Mathematical Puzzle
[Re: muzza]
|
carpal tunnel
Registered: 08/03/2000
Posts: 12318
Loc: Sterling, VA
|
"Why a spoon, cousin? Why not an axe?"
"Cause it's dull, you twit, it'll hurt more!"
_________________________
Matt
|
Top
|
|
|
|
#105466 - 18/07/2002 08:09
Re: Puzzle
[Re: tanstaafl.]
|
addict
Registered: 23/01/2002
Posts: 506
Loc: The Great Pacific NorthWest
|
Actually John never says that the other guy is walking. Maybe the other guy would hitchhike. Its would be faster. Maybe the other guy has a skateboard, a pod racer, a teleportation booth?
_________________________
No matter where you might be, there you are.
|
Top
|
|
|
|
#105467 - 18/07/2002 08:13
Re: Mathematical Puzzle
[Re: mschrag]
|
old hand
Registered: 30/07/2001
Posts: 1115
Loc: Lochcarron and Edinburgh
|
In reply to:
I think you have to define x_2 explicitly .. My brain can't comprehend why,
Yeah, I don't understand it either, as the original equation defines x_2 correctly. Perhaps there's a hidden divide-by-zero in the derivation (a bit like the one in the standard "proof" that 1=2).
Anyway, back to my DSSSL hacking - I've almost got something that interprets a user tag "print" to decide whether or not to output each subtree.
_________________________
Toby Speight 030103016 (80GB Mk2a, blue) 030102806 (0GB Mk2a, blue)
|
Top
|
|
|
|
#105468 - 18/07/2002 08:43
Re: Mathematical Puzzle
[Re: muzza]
|
addict
Registered: 25/06/2002
Posts: 456
|
In reply to:
Try a runsable spoon. not as sharp but quite effective.
runcible?
|
Top
|
|
|
|
#105469 - 18/07/2002 11:01
Re: Mathematical Puzzle
[Re: tms13]
|
pooh-bah
Registered: 09/09/2000
Posts: 2303
Loc: Richmond, VA
|
I was thinking you could maybe get a little further because you know x_n was an integer and you could define:
since x_n was an integer, x_n = y / (n - 1) where y is an integer (1 + sum...). I haven't tried it yet, but I wonder if you sub that in to the x_{n+1}, does it get you any further (does that (n-1) cancel anything out). The next step has got to be that you take advantage of the fact that you know the previous number was an integer ........
ms
|
Top
|
|
|
|
#105470 - 18/07/2002 11:54
Re: Puzzle
[Re: tanstaafl.]
|
journeyman
Registered: 30/01/2002
Posts: 87
Loc: Texas
|
If you assume:
1. John and Fred walk the same speed
2. John and Fred ride the same speed
3. Lamposts are evenly spaced
4. Each section of travel is bounded by start point, town, or a lamp post.
5. There is a lamp post at the start and stop points, or the distance from the start or stop point to the nearest lamp post is the same as from lamp post to lamp post.
6. DELTA=(section walk time)-(section ride time)
7. They Ride faster than they walk.
John is correct.
For an even number of sections John and Fred will both arrive at town sooner (and at the same time). For each pair of sections, they will reduce there travel time by DELTA.
If the number of sections is odd, the scenario is the same as above except that John will arrive at town first and shave an additional DELTA off of his travel time (Fred gets no additional travel time reduction).
Since John concocted the proposition, perhaps he does not intend to chain up the bike to the first lamp post at all...
_________________________
MK2a 160GB
11 Years later, these Mk2a units still rock...
|
Top
|
|
|
|
#105472 - 19/07/2002 00:43
Re: Puzzle
[Re: lamer]
|
Anonymous
Unregistered
|
"Since John concocted the proposition, perhaps he does not intend to chain up the bike to the first lamp post at all... "
damn, you made me crack me up
|
Top
|
|
|
|
#105474 - 19/07/2002 03:21
Re: Mathematical Puzzle
[Re: tfabris]
|
carpal tunnel
Registered: 13/07/2000
Posts: 4174
Loc: Cambridge, England
|
If you continue to use algebra on the BBS, I will have to hunt you down and kill you. Slowly. With a very dull knife.
So MathML in posts is enabled only for moderators?
Peter
|
Top
|
|
|
|
#105475 - 19/07/2002 15:15
Re: Mathematical Puzzle
[Re: music]
|
Pooh-Bah
Registered: 21/07/1999
Posts: 1765
Loc: Brisbane, Queensland, Australi...
|
Sorry runcible spoon. I'm sure that's the spelling I had before.
_________________________
--
Murray
I What part of 'no' don't you understand?
Is it the 'N', or the 'Zero'?
|
Top
|
|
|
|
#105476 - 19/07/2002 16:55
Re: Mathematical Puzzle
[Re: muzza]
|
carpal tunnel
Registered: 08/03/2000
Posts: 12318
Loc: Sterling, VA
|
So it's a spork, right?? Oh, it has a cutting edge....
A knorkoon?
_________________________
Matt
|
Top
|
|
|
|
#105478 - 19/07/2002 17:13
Re: Mathematical Puzzle
[Re: lectric]
|
pooh-bah
Registered: 20/01/2002
Posts: 2085
Loc: New Orleans, LA
|
Oh wait... you weren't talking to me.. I was refering to my equasion earlier on the walking thingie... the 2 on the bottom is incorrect, it should be 2X. Since all the trials I had tried were using 1 mph as x, it always worked, but it would NOT have worked if the speeds were 2mph and 5mph, respectively. anyway, blech.
|
Top
|
|
|
|
#105479 - 19/07/2002 19:19
Re: Mathematical Puzzle
[Re: muzza]
|
carpal tunnel
Registered: 13/02/2002
Posts: 3212
Loc: Portland, OR
|
Sorry runcible spoon.
Ah, nifty. In your first post, I thought you'd just horribly butchered the spelling of re-usable.
I guess that answers the Chunky Cambells Soup question...
|
Top
|
|
|
|
#105481 - 03/05/2004 09:21
Re: Puzzle
[Re: tfabris]
|
new poster
Registered: 13/04/2004
Posts: 5
|
Ah, this brings back memories.
|
Top
|
|
|
|
#105482 - 06/05/2004 01:34
Re: Puzzle
[Re: tfabris]
|
carpal tunnel
Registered: 08/07/1999
Posts: 5543
Loc: Ajijic, Mexico
|
Do you get anything, like a mug or a Shameless Commerce gift certificate?
Naaah... they only give that stuff to the people who get the correct answer to the puzzler.
tanstaafl.
_________________________
"There Ain't No Such Thing As A Free Lunch"
|
Top
|
|
|
|
|
|