Given $ n$ points arbitrarily in the plane $ P_{1},P_{2},\ldots,P_{n},$ among them no three points are collinear. Each of $ P_{i}$ ($1\le i\le n$) is colored red or blue arbitrarily. Let $ S$ be the set of triangles having $ \{P_{1},P_{2},\ldots,P_{n}\}$ as vertices, and having the following property: for any two segments $ P_{i}P_{j}$ and $ P_{u}P_{v},$ the number of triangles having $ P_{i}P_{j}$ as side and the number of triangles having $ P_{u}P_{v}$ as side are the same in $ S.$ Find the least $ n$ such that in $ S$ there exist two triangles, the vertices of each triangle having the same color.
Problem
Source: Chinese TST 2007 5th quiz P2
Tags: combinatorics proposed, combinatorics
hxy09
25.12.2009 17:07
Merry Christmas!!! We will show $ n_{min}=8$ here we go: Suppose there are exactly $ k$ triangles containing a certain segment $ P_iP_j$ where $ K$ is independent from $ i,j$ Thus $ |S|=\frac{1}{3}k\binom{n}{2}$ Let's compute the number,call it $ x$,of triangles with vertices of two colors Denote $ n_1,n_2$ the number of blue vertices and red vertices For every triangle with vertices of two colors has exactly two sides whose vertices are of different colors this yields $ x=\frac{1}{2}kn_1n_2$ $ \frac{1}{3}k\binom{n}{2}-\frac{1}{2}kn_1n_2\ge 2$ yields $ n\ge 8$ What we need now is just a counterexample for the case $ n=7$ We paint $ 1,2,3$ red,$ 4,5,6,7$ blue and take a look at $ (456)(347)(167)(257)(236)(135)(124)$ We're done!
Stranger8
25.10.2016 11:11
hxy09 wrote: Merry Christmas!!! We will show $ n_{min}=8$ here we go: Suppose there are exactly $ k$ triangles containing a certain segment $ P_iP_j$ where $ K$ is independent from $ i,j$ Thus $ |S|=\frac{1}{3}k\binom{n}{2}$ Let's compute the number,call it $ x$,of triangles with vertices of two colors Denote $ n_1,n_2$ the number of blue vertices and red vertices For every triangle with vertices of two colors has exactly two sides whose vertices are of different colors this yields $ x=\frac{1}{2}kn_1n_2$ $ \frac{1}{3}k\binom{n}{2}-\frac{1}{2}kn_1n_2\ge 2$ yields $ n\ge 8$ What we need now is just a counterexample for the case $ n=7$ We paint $ 1,2,3$ red,$ 4,5,6,7$ blue and take a look at $ (456)(347)(167)(257)(236)(135)(124)$ We're done! but you didn't show that if integer＄n＄does not satisfy the condition,then the integer which is smaller than ＄n＄ doesn't satisfy the condition,either.In fact,the case ＄n＄=6 are not so.easy to find a counterexample.
Skravin
25.10.2016 12:57
Stranger8 wrote: hxy09 wrote: Merry Christmas!!! We will show $ n_{min}=8$ here we go: Suppose there are exactly $ k$ triangles containing a certain segment $ P_iP_j$ where $ K$ is independent from $ i,j$ Thus $ |S|=\frac{1}{3}k\binom{n}{2}$ Let's compute the number,call it $ x$,of triangles with vertices of two colors Denote $ n_1,n_2$ the number of blue vertices and red vertices For every triangle with vertices of two colors has exactly two sides whose vertices are of different colors this yields $ x=\frac{1}{2}kn_1n_2$ $ \frac{1}{3}k\binom{n}{2}-\frac{1}{2}kn_1n_2\ge 2$ yields $ n\ge 8$ What we need now is just a counterexample for the case $ n=7$ We paint $ 1,2,3$ red,$ 4,5,6,7$ blue and take a look at $ (456)(347)(167)(257)(236)(135)(124)$ We're done! but you didn't show that if integer＄n＄does not satisfy the condition,then the integer which is smaller than ＄n＄ doesn't satisfy the condition,either.In fact,the case ＄n＄=6 are not so.easy to find a counterexample. ?? how the latex isn't applied?