wu :: forums - Print Page


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

        riddles >> hard >> jumping frog
        
(Message started by: kyle1080 on Sep 30^th, 2009, 9:52am)

Title: jumping frog
Post by kyle1080 on Sep 30^th, 2009, 9:52am

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.

Title: Re: jumping frog
Post by jpk2009 on Sep 30^th, 2009, 4:08pm

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. :-/

Title: Re: jumping frog
Post by Obob on Sep 30^th, 2009, 5:38pm

You don't get to choose what X is. It is given to you.

Title: Re: jumping frog
Post by jpk2009 on Sep 30^th, 2009, 7:09pm

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.

Title: Re: jumping frog
Post by Obob on Sep 30^th, 2009, 8:14pm

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.

Title: Re: jumping frog
Post by jpk2009 on Sep 30^th, 2009, 8:44pm

Gotcha. Thanks!

Title: Re: jumping frog
Post by JohanC on Oct 1^st, 2009, 2:22pm

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

Title: Re: jumping frog
Post by Obob on Oct 1^st, 2009, 3:54pm

Of course that's the same. I didn't propose the original question, though.

Title: Re: jumping frog
Post by JohanC on Oct 2^nd, 2009, 6:45am

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.

[hide]The solution I have in mind involves recursively putting pigeons outside their holes .... [/hide]

Anyway, it's a nice little puzzle.

Title: Re: jumping frog
Post by Obob on Oct 2^nd, 2009, 6:52am

Care to elaborate? I've thought about it a bit, but couldn't think of an immediate recursive solution.

Title: Re: jumping frog
Post by Michael Dagg on Oct 4^th, 2009, 2:48pm

That's not exactly trivial. I see one way to do it.

Title: Re: jumping frog
Post by R on Oct 19^th, 2009, 4:47am

One last doubt:
Can the frog make jump of one particular size, say a_i, more than once?
I read all the replies, excuse me, If someone has already answered it and I didn't notice.

Title: Re: jumping frog
Post by rmsgrey on Oct 19^th, 2009, 2:42pm

on 10/19/09 at 04:47:19, R wrote:

One last doubt:
Can the frog make jump of one particular size, say a_i, 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...

Title: Re: jumping frog
Post by R on Oct 20^th, 2009, 1:12pm

Can Induction work here?
[hide]
For base case n = 2, it is true. We have a₁ and a₂.
If X = {a₁}, then we can have jumps in order a₂, a₁.
If X = {a₂}, then we can have jumps in order a₁, a₂.
else
in any order.

Assuming the hypothesis to be true for some n, we have a₁, a₂, ... a_n and X = {x₁, x₂... , x_n-1} And no mark in X is touched by any jump. If we add one more jump-size a_n+1 to it, and also add x_n s.t. x_n = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif a_i for 1<=i<=n, in worst case. Then we can have the jump order changed to a₁, a₂, ... a_n+1, a_n so that no mark is touched by any jump.
Hence Proved!!![/hide]
I think I haven't done it correctly.

Title: Re: jumping frog
Post by Obob on Oct 20^th, 2009, 4:16pm

on 10/20/09 at 13:12:57, R wrote:

If we add one more jump-size a_n+1 to it, and also add x_n s.t. x_n = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif a_i for 1<=i<=n, in worst case. Then we can have the jump order changed to a₁, a₂, ... a_n+1, a_n so that no mark is touched by any jump.

This isn't correct. You have a problem any time x_n equals any of the places visited by the previous path of jumps; not just when x_n equals the last place that was visited.

I still don't know a correct solution, though.