LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   *ANSWER* Q9 (fairly long, not complete) (http://book.caltech.edu/bookforum/showthread.php?t=4841)

 skbaek90 07-13-2018 02:16 PM

*ANSWER* Q9 (fairly long, not complete)

First, my understanding of the problem's background.

Dr. Yaser has mentioned in previous threads that there are no systematic way of doing this problem, but that placing the points on the perimeter of a circle is a good start.

From what I understand, this ensures that if you can't shatter k points on the perimeter of a circle with a triangle, then you can't shatter the k points with a triangle no matter how you place them and thus k is the break point.

Now, my reasoning about why 7 is correct. To shatter 7 points, you either shatter the 7 points into

Case 1: 0 & 7
Case 2: 1 & 6
Case 3: 2 & 5
Case 4: 3 & 4
... and so forth, where, let's say, the number on the left represents the number of +1's and the right the number of -1's.

You are basically separating the 7 points by connecting 3 points on the circle (thereby forming a triangle). Case 1 ~ 4 is easily handled because for Case 3, for example, you just pick 2 points as vertices of the triangle and pick somewhere on the circle that is NOT a point, thus including the 2 points and excluding the rest, the 5 points.

Case 5 ~ 8 is where I am stuck, but I feel like it still has to do with the fact that Case 5: 4 & 3, where we can shatter using a triangle (3 vertices) and that number 3 is included in Case 5.

Also, if you think about why 9 is not the correct answer, when you try to shatter 9, it breaks down into the following cases:

Case 1) 0 & 9
Case 2) 1 & 8
Case 3) 2 & 7
Case 4) 3 & 6
Case 5) 4 & 5
and so on..

If you look at case 5, you have to define the region for 4 points, or 5 points using only a triangle (which only has 3 vertices). Therefore, it's not possible to shatter 9 points.

This is my understanding of the answer, although not complete. Please correct me if I'm wrong. :clueless:

 AlexS 01-24-2020 10:56 AM

Re: *ANSWER* Q9 (fairly long, not complete)

Quote:
 Originally Posted by skbaek90 (Post 13073) First, my understanding of the problem's background. Dr. Yaser has mentioned in previous threads that there are no systematic way of doing this problem, but that placing the points on the perimeter of a circle is a good start. From what I understand, this ensures that if you can't shatter k points on the perimeter of a circle with a triangle, then you can't shatter the k points with a triangle no matter how you place them and thus k is the break point. Now, my reasoning about why 7 is correct. To shatter 7 points, you either shatter the 7 points into Case 1: 0 & 7 Case 2: 1 & 6 Case 3: 2 & 5 Case 4: 3 & 4 ... and so forth, where, let's say, the number on the left represents the number of +1's and the right the number of -1's. You are basically separating the 7 points by connecting 3 points on the circle (thereby forming a triangle). Case 1 ~ 4 is easily handled because for Case 3, for example, you just pick 2 points as vertices of the triangle and pick somewhere on the circle that is ASO a point, thus including the 2 points and excluding the rest, the 5 points. Case 5 ~ 8 is where I am stuck, but I feel like it still has to do with the fact that Case 5: 4 & 3, where we can shatter using a triangle (3 vertices) and that number 3 is included in Case 5. Also, if you think about why 9 is not the correct answer, when you try to shatter 9, it breaks down into the following cases: Case 1) 0 & 9 Case 2) 1 & 8 Case 3) 2 & 7 Case 4) 3 & 6 Case 5) 4 & 5 and so on.. If you look at case 5, you have to define the region for 4 points, or 5 points using only a triangle (which only has 3 vertices). Therefore, it's not possible to shatter 9 points. This is my understanding of the answer, although not complete. Please correct me if I'm wrong. :clueless:
very nice case do you have more?

 All times are GMT -7. The time now is 06:10 PM.