LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)

 arcticblue 04-20-2013 11:47 PM

Q6

I am unsure what is meant by 2 intervals. Is this a valid layout for 2 intervals?
x|o|x|o|x
Or does it mean?
x|o|x

And to find the breakpoint I presume all I need to do is find a layout where the N points can't be successfully put into the M intervals.
eg
N=4 (xoxo) would be a breakpoint for the second option above if my understanding is correct.

Since there aren't any questions about Q6/Q8 I'm guessing I've just misunderstood the problem or haven't understood part of the lecture. Any advice would be appreciated.

 marek 04-20-2013 11:56 PM

Re: Q6

There are a few other threads about the multiple interval questions, so you're not alone. In summary, both of your scenarios are valid, depending on the context. But rather than repeat what is in those threads, it's perhaps best that you check them out directly.

 marek 04-21-2013 12:06 AM

Re: Q6

I'll give one concrete numerical example to hopefully set you on the right path.

Lets say I am considering N = 3 and pick points {1, 7, 11}. Can I find a way to set up two intervals to get all possible 2^3 = 8 possible dichotomies? By your short hand I'm assuming o represents +1 and x represents -1.

If I want the arrangment xox, that means 1 and 11 have to be outside my choices for intervals and 7 has to be inside. So one particular choice of intervals would be [5,9] and [99,100]. Another would be [5,8] and [6,10]. You can go easily verify that all possible 2^3 arrangements are possible. The only trick here is that you're restricted by the geometry of an interval, meaning it starts at one particular value, ends at another, and contains every point in between.

 arcticblue 04-21-2013 01:58 AM

Re: Q6

Okay so it seems like my understanding is correct. And if we take the case of M=1 which should match up with the example given in lecture 5. Here it's possible to find a setup which splits N=3 correctly for all 8 combinations. So then for M=1 the breakpoint must be at least 4 since 3 points can be satisfied. But then in Q8 the general case M=1 must be 4 or greater since the breakpoint is 4 or more, however for M=1 the largest option is a breakpoint of 3.

So I guess Q8 is confusing me for Q6. I must be misunderstanding something except I think I understand how the breakpoint number works and I think my understanding of the example in the lecture is correct. Any ideas on what I've missed?

 marek 04-21-2013 09:50 AM

Re: Q6

Quote:
 Originally Posted by arcticblue (Post 10523) Okay so it seems like my understanding is correct. And if we take the case of M=1 which should match up with the example given in lecture 5. Here it's possible to find a setup which splits N=3 correctly for all 8 combinations. So then for M=1 the breakpoint must be at least 4 since 3 points can be satisfied. But then in Q8 the general case M=1 must be 4 or greater since the breakpoint is 4 or more, however for M=1 the largest option is a breakpoint of 3. So I guess Q8 is confusing me for Q6. I must be misunderstanding something except I think I understand how the breakpoint number works and I think my understanding of the example in the lecture is correct. Any ideas on what I've missed?
For M=1, N = 3, the breakpoint is not 4. It is 3. Double check all 8 configurations. You should find one that you cannot obtain with just 1 interval.

 arcticblue 04-21-2013 03:42 PM

Re: Q6

Thanks Marek I now see what I was doing wrong. Everything makes sense now. :)

 All times are GMT -7. The time now is 07:57 PM.