uniolympiads English

IMC 2014, Ημέρα 2, Θέμα 4

We say that a subset of Rn\mathbb{R}^n is kk-almost contained by a hyperplane if there are less than kk points in that set which do not belong to the hyperplane. We call a finite set of points kk-generic if there is no hyperplane that kk-almost contains the set. For each pair of positive integers kk and nn, find the minimal number d(k,n)d(k, n) such that every finite kk-generic set in Rn\mathbb{R}^n contains a kk-generic subset with at most d(k,n)d(k, n) elements.

Πρωτότυπο από το επίσημο PDFWe say that a subset of R n is k -almost ontained by a hyperplane if there are less than k points in that set whi h do not belong to the hyperplane. We all a nite set of points k -generi if there is no hyperplane that k -almost ontains the set. For ea h pair of positive integers k and n , nd the minimal number d(k, n) su h that every nite k -generi set in R n ontains a k -generi subset with at most d(k, n) elements. Problem 4.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Shachar Carmeli, Weizmann Inst. and Lev Radzivilovsky, Tel Aviv Univ.)

Solution. The answer is: d(k,n)={k⋅nk,n>1k+notherwised(k,n) = \begin{cases} k\cdot n & k,n > 1 \\ k+n & \text{otherwise} \end{cases}

Throughout the solution, we shall often say that a hyperplanes skips a point to signify that the plane does not contain that point.

For n=1n = 1 the claim is obvious.

For k=1k = 1 we have an arbitrary finite set of points in Rn\mathbb R^n such that neither hyperplane contains it entirely. We can build a subset of n+1n+1 points step by step: on each step we add a point, not contained in the minimal plane spanned by the previous points. Thus any 1-generic set contains a non-degenerate simplex of n+1n+1 points, and obviously a non-degenerate simplex of n+1n+1 points cannot be reduced without loosing 1-generality.

In the case k,n>1k,n > 1 we shall give an example of k⋅nk\cdot n points. On each of the Cartesian axes choose kk distinct points, different from the origin. Let's show that this set is kk-generic. There are two types of planes: containing the origin and skipping it. If a plane contains the origin, it either contains all the chose points of a axis or skips all of them. Since no plane contains all axes, it skips the kk chosen points on one of the axes. If a plane skips the origin, it it contains at most one point of each axis. Therefore it skips at least n(k−1)n(k-1) points. It remains to verify a simple inequality n(k−1)≥kn(k-1) \ge k which is equivalent to (n−1)(k−1)≥1(n-1)(k-1) \ge 1 which holds for n,k>1n,k > 1.

The example we have shown is minimal by inclusion: if any point is removed, say a point from axis ii, then the hyperplane xi=0x_i = 0 skips only k−1k-1 points, and our set stops being kk-generic. Hence d(k,n)≥knd(k,n) \ge kn.

It remains to prove that Hence d(k,n)≥knd(k,n) \ge kn for k,n>1k,n > 1, meaning: for each kk-generic finite set of points, it is possible to choose a kk-generic subset of at most knkn points. Let us call a subset of points minimal if by taking out any point, we loose kk-generality. It suffices to prove that any minimal kk-generic subset in Rn\mathbb R^n has at most knkn points. A hyperplane will be called ample if it skips precisely kk points. A point cannot be removed from a kk-generic set, if and only if it is skipped by an ample hyperplane. Thus, in a minimal set each point is skipped by an ample hyperplane.

Organise the following process: on each step we choose an ample hyperplane, and paint blue all the points which are skipped by it. Each time we choose an ample hyperplane, which skips one of the unpainted points. The unpainted points at each step (after the beginning) is the intersection of all chosen hyperplanes. The intersection set of chosen hyperplanes is reduced with each step (since at least one point is being painted on each step).

Notice, that on each step we paint at most kk points. So if we start with a minimal set of more then nknk points, we can choose nn planes and still have at least one unpainted points. The intersection of the chosen planes is a point (since on each step the dimension of the intersection plane was reduced), so there are at most nk+1nk+1 points in the set. The last unpainted point will be denoted by OO. The last unpainted line (which was formed on the step before the last) will be denoted by ℓ1\ell_1.

This line is an intersection of all the chosen hyperplanes except the last one. If we have more than nknk points, then ℓ1\ell_1 contains exactly k+1k+1 points from the set, one of which is OO.

We could have executed the same process with choosing the same hyperplanes, but in different order. Anyway, at each step we would paint at most kk points, and after nn steps only OO would remain unpainted; so it was precisely kk points on each step. On step before the last, we might get a different line, which is intersection of all planes except the last one. The lines obtained in this way will be denoted ℓ1,ℓ2,...,ℓn\ell_1, \ell_2, ..., \ell_n, and each contains exactly kk points except OO. Since we have OO and kk points on nn lines, that is the entire set. Notice that the vectors spanning these lines are linearly independent (since for each line we have a hyperplane containing all the other lines except that line). So by removing OO we obtain the example that we've described already, which is kk-generic.

Remark. From the proof we see, that the example is unique.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;