(1) Let $S$ be a set of at least $n+2$ points in $R^n$. Prove that $S$ can be partitioned into two subsets whose convex hulls intersect.

(2) Let $C_1, \dots, C_m$ be convex sets in $R^n$ such that any $n+1$ of them intersect. Prove that all of them intersect.

(3) Let $p$ be a fixed prime. Construct a family of $\Omega (n^3)$ subsets of $\{1, \dots, n \}$ such that each has cardinality $p^3$ but any two has intersection
either 0, 1, $p$ or $p^2$.

(4)* Let $F$ be a family of subsets of $\{1, \dots, n \}$ such that the intersection of any three is even. Prove that for all sufficiently large $n$, $|F| \le 2^{n/2}$.

(*) is a bonus problem, it does not count if you cannot do it, but if you can, I am willing to hear the solution.

From → Không phân loại

4 phản hồi
1. Very interesting problems!

(1) If a point is inside the CH of the other n+1, can that be considered an answer?

(4) I’m just curious, are you discussing the dimensionality argument in class? I think I’ve seen the version where the intersection of every two is even, where the dimensionality argument was used.

• Dear Hung

(1) Yes, I think so.

(2) Yes, we did have that argument which works for intersection of 2.

2. BTW, bác Văn, what if somebody posts a solution here and a student in your class sees it?

• The due date is next Thursday, so if you do after that, it is OK. Also if it is in Vietnamese, then it may be safe, unless they apply some good translating program.