Author |
Topic: jumping frog (Read 2081 times) |
|
kyle1080
Newbie
Posts: 6
|
 |
jumping frog
« on: Sep 30th, 2009, 9:52am » |
 Quote  Modify
|
a1,a2,...,an are distinct positive integers and X is a set of n-1 positive integers not containing s = \sum ak, k=1 to n. A frog is to jump around on the real axis, starting at the point 0 and making n jumps to the right with lengths a1,a2,...,an in some order. Determine that the order can be chosen in such a way that the frog never lands on any point in X.
|
|
 IP Logged |
|
|
|
jpk2009
Junior Member
Gender: 
Posts: 60
|
|
Re: jumping frog
« Reply #1 on: Sep 30th, 2009, 4:08pm » |
Quote Modify
|
The problem seems easy, so I probably got it wrong. If n = 1 and say a1 = 1 then X is empty. So the frog can jump form 0 to 1 but 1 is not it X because it is empty. If n = 2 and a1 = 1 and a2 = 2 then s = 3. But the problem says that X is just a set of positive integers not containing s. So, pick X = {11}. It does not contain 3 and the frog can make jumps of 1,2, and 3 lengths in that order, landing on 1,3,6. None of these numbers are in X either. Looking at n = 3 this also can be done. There must be something more about the set X that I don't understand.
I messed X up for n = 2 at first but fixed it. It just seems that as long as the smallest integer in X is greater than s then it will always work. I thought that maybe X needs to be all of the positive integers excluding s but it says n-1 integers. :-/
|
| « Last Edit: Sep 30th, 2009, 4:35pm by jpk2009 » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender: 
Posts: 489
|
|
Re: jumping frog
« Reply #2 on: Sep 30th, 2009, 5:38pm » |
Quote Modify
|
You don't get to choose what X is. It is given to you.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: jumping frog
« Reply #3 on: Sep 30th, 2009, 7:09pm » |
Quote Modify
|
I thought I was missing something but please explain X. It says that X is a set of n-1 positive integers not containing the sum s = a1 + a2 + ... + an. To me that means that X can, well, be a any set containing n-1 positive integers but one of them is not the sum s.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: jumping frog
« Reply #4 on: Sep 30th, 2009, 8:14pm » |
Quote Modify
|
Yes, it means that it can be any set of n-1 numbers not containing s. Which means that you have to show that no matter what set of n-1 numbers it is, you can find a way of hopping over them. Not that for one particular set of n-1 numbers you can do so.
The numbers a1,...,an are also arbitrary distinct positive integers: you don't get to pick what they are.
So the problem is as follows: I tell you some distinct positive integers a1,...,an, and n-1 distinct positive integers b1,...,b{n-1}, none of which equal a1+...+an. Now you have to tell me how the frog can make n leaps of sizes a1,...,an in some order so that he avoids all the integers bi.
To illustrate by exaggeration, if I ask you to "prove that the square of any integer is a positive number" you can't say "(-1)^2 = 1 is positive" as a solution.
|
|
IP Logged |
|
|
|
jpk2009
Junior Member
Gender:
Posts: 60
|
|
Re: jumping frog
« Reply #5 on: Sep 30th, 2009, 8:44pm » |
Quote Modify
|
Gotcha. Thanks!
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: jumping frog
« Reply #6 on: Oct 1st, 2009, 2:22pm » |
Quote Modify
|
Hi, Obob,
Would it make sense to refrase the question as:
You are given n sticks a_i with all different integer lenghts.
On a road markers b_i are placed at n-1 different spots, but not at position 0 nor at the position s (s being the sum of the lengths of all the sticks).
The goal is to proof (e.g. by giving an algorithm or maybe via a clever pigeon hole trick) that the sticks can be laid down one after another in such a way that no sticks ends on a marker.
It is clear that position s will always be touched, and markers further away will never be reached.
My feeling is that such a description would make the problem easier to grasp. A jumping frog just seems too difficult to control 
JohanC
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: jumping frog
« Reply #7 on: Oct 1st, 2009, 3:54pm » |
Quote Modify
|
Of course that's the same. I didn't propose the original question, though.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: jumping frog
« Reply #8 on: Oct 2nd, 2009, 6:45am » |
Quote Modify
|
Yes, I noticed you weren't the original poster, but you seemed to be quite familiar (or at least comfortable) with this puzzle. Therefore, my idea to check with you that I understood everything correctly.
After rewriting, I get the impression it's a problem that Towr would move to medium, or even to easy.
The solution I have in mind involves recursively putting pigeons outside their holes ....
Anyway, it's a nice little puzzle.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: jumping frog
« Reply #9 on: Oct 2nd, 2009, 6:52am » |
Quote Modify
|
Care to elaborate? I've thought about it a bit, but couldn't think of an immediate recursive solution.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: jumping frog
« Reply #10 on: Oct 4th, 2009, 2:48pm » |
Quote Modify
|
That's not exactly trivial. I see one way to do it.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: jumping frog
« Reply #11 on: Oct 19th, 2009, 4:47am » |
Quote Modify
|
One last doubt:
Can the frog make jump of one particular size, say ai, more than once?
I read all the replies, excuse me, If someone has already answered it and I didn't notice.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: jumping frog
« Reply #12 on: Oct 19th, 2009, 2:42pm » |
Quote Modify
|
on Oct 19th, 2009, 4:47am, R wrote:One last doubt:
Can the frog make jump of one particular size, say ai, more than once?
I read all the replies, excuse me, If someone has already answered it and I didn't notice. |
|
He has to make exactly n jumps, and use n different numbers, which doesn't leave any room for repeats...
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: jumping frog
« Reply #13 on: Oct 20th, 2009, 1:12pm » |
Quote Modify
|
Can Induction work here?
For base case n = 2, it is true. We have a1 and a2.
If X = {a1}, then we can have jumps in order a2, a1.
If X = {a2}, then we can have jumps in order a1, a2.
else
in any order.
Assuming the hypothesis to be true for some n, we have a1, a2, ... an and X = {x1, x2... , xn-1} And no mark in X is touched by any jump. If we add one more jump-size an+1 to it, and also add xn s.t. xn =  ai for 1<=i<=n, in worst case. Then we can have the jump order changed to a1, a2, ... an+1, an so that no mark is touched by any jump.
Hence Proved!!!
I think I haven't done it correctly.
|
| « Last Edit: Oct 20th, 2009, 1:21pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: jumping frog
« Reply #14 on: Oct 20th, 2009, 4:16pm » |
Quote Modify
|
on Oct 20th, 2009, 1:12pm, R wrote:If we add one more jump-size an+1 to it, and also add xn s.t. xn = ai for 1<=i<=n, in worst case. Then we can have the jump order changed to a1, a2, ... an+1, an so that no mark is touched by any jump.
|
|
This isn't correct. You have a problem any time xn equals any of the places visited by the previous path of jumps; not just when xn equals the last place that was visited.
I still don't know a correct solution, though.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print