LFD Book Forum *ANSWER* Q9 (fairly long, not complete)
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
07-13-2018, 02:16 PM
 skbaek90 Junior Member Join Date: Jul 2018 Posts: 1
*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.