Consider the greatest set such that doesn't contain any group, ($ A$). If this set has $ 10$ or more elements, we are done. If the set has less than $ 10$ elements, there are at least $ 37$ students that don't belong to it. If you take any of these and add it to $ A$, then by hypothesis you will get a $ 3$-group. So, each of the (al least $ 37$) students out of $ A$ form a $ 3$-set with other two belonging to $ A$. As we have at most $ 9$ people in $ A$, we have at most $ 36$ pairs of elements in it. So, there is a pair of $ A$-elements that form $ 3$-sets (pigeonhole) with at least two others out of $ A$. This means there are two $ 3$-sets having $ 2$ members in common, contradiction. So $ A$ must have at least $ 10$ elements.

Beautiful argument, Nemion! Here's my way: Choose any 2 people, call them 1 and 2. There is at most one other who is in a group with both 1 and 2; call him 3 (if he exists). So choose any person different from 1,2,3, say person 4. There are at most 2 others who are in a group with 2 of {1,2,4}; call them 5,6 (if they exist). So choose someone different from 1,..,6 call him 7. There are at most 3 others in a group with 2 of {1,2,4,7}, call them 8,9,10 (if they exist). Continuing in this fashion, we choose people 1,2,4,7,11,16,22,29,37,46. Among these 10 people, no group is contained. Define the sequence G1=1,G2=2,G(m+1)=G(m)+G(m-1) for m>2. Let G_k be the largest term in the sequence that is at most N. Then among N people, there must exist a set of k people in which no group is contained.

Your recurrence for $G(m)$ is wrong. According to your method, it's $G(m) = \dfrac {m^2-m+2}{2}$

Oops I meant G1=1, G(m+1)=G(m)+m which indeed yields the above expression.

What does properly contained mean? ex. For the person (1,2,...,10),can the groups be (1,2,3),(4,5,6),(7,8,9),(10,20,30)?

Wrong

Could you tell me if there is a problem with my solution please? We create a graph with $46$ vertices and edges between people in the same group. By supposition there is only triangles or two triangle with a vertices in common in this graph. Thus we can color it with $3$ colors. So there is a group of $ \lfloor 46/3 \rfloor + 1 = 16$ vertices of the same color which means that we can pick $16$ people such that any of them are not in the same group. Everything seems fine but I'm surprised that I'm getting $16 > 10$ so I may have missed something.

APMO 2008/2 wrote: Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is $ 46$, there is a set of $ 10$ students in which no group is properly contained. Let $S$ be the largest set of students in which no group is properly contained (pick any set $S$ if there are several of them). Let $S$ have $t$ students. Note that adding any student $u$ not in $S$; there exist $v, w$ in $S$ such that $u, v, w$ form a group. Hence we have defined an injection from the set of remaining students to the set of pairs of elements of $S$. Comparing sizes, we see that $$46-t \le \binom{t}{2} \implies t \ge 10$$just as we desired. $\blacksquare$

The key to this problem is realizing that 46=10+9C2 Suppose we have a random set of 10 people labeled 1 to 10, if there are no groups represented, then we are done. We prove that we can always lower the number of groups included. Suppose peoples 1,2,3 are in a group wlog. There are 36 people outside of the group. (Notice that a pair of people(i,j) can appear in at most 1 group. Call a pair i,j good if 0<i<j<11 and neither i nor j are 3, there are 9C2=36 good pairs.) If any of these 36 people are not in a group with a good pair, then we can swap this guy with person 3, and so the total number of groups included is lowered. Suppose there are no such people, since there are only 36 good pairs, and each good pair can only be in 1 group, we see that there exists a person in the set of 36 that is grouped with the pair 1,2. But that means 1,2 are in 2 groups which is a contradiction. Therefor, if there is more than 0 groups included, we can always decrease the total number of groups included.

This problem is also basically a 1999 Italy TST problem: Quote: [Italy TST 1999] Let $X$ be an $n$-element set and let $A_1, A_2, \cdots, A_m$ be subsets of $X$ such that: (i) $|A_i| = 3$ for $i = 1, 2, \cdots, m$ (ii) $|A_i \cap A_j| = 1$ for any two distinct indices $i, j.$ Show that there exists a subset of $X$ with at least $\lfloor \sqrt{2n} \rfloor$ elements which does not contain any of the $A_i$’s.

Quote: Consider the greatest set such that doesn't contain any group, ($ A$). Quote: Let $S$ be the largest subset of $X$ that does not contain any of the $A_i$'s. FWIW, I don't think one can speak of the largest subset in this context, but it suffices for the argument in both cases to consider a subset of maximal size.

APMO 2008 P2. Students in a class form groups, each of which contains exactly three members, such that any two distinct groups have at most one member in common. Show that when the class size is $46$, there exists a set of $10$ students in which no group is properly contained. Solution 1. We claim that when the class size is $\binom{n}{2}+1$ there exists a required set of $n$ elements and proceed by induction. The base case $n=3$ is trivial. Now in a class of size $\binom{n+1}{2}+1$ by induction hypothesis there exists a required set of $n$ elements. Now note that any two students can belong to at most one common group, so there are at most $\binom{n}{2}$ groups in the required set, hence there is $\binom{n+1}{2}+1-\binom{n}{2}-n=1$ student left and he could be added to the required set without any problem. Solution 2. Consider the largest subset $S$ of the set of all $46$ students. Assume on the contrary that $|S|\le 9$. Then the number of groups in $S$ is at most $\binom{9}{2}=36$ since any two students can belong to at most one common group, but there are at least $37$ students outside $S$, a contradiction to the maximality of $S$.

Surprisingly tricky for APMO 2. We will build the set inductively, starting with an arbitrary set of $2$ students. If at any point the set has $k\le 9$ students, then at most $\binom{k}{2}$ pairs can be in a group with a student outside of the set. Since there are at least $46 - k\ge 37 > \binom{k}{2}$ students outside of the set, we can find a student that won't induce any groups, as desired.

can we do this with halls

Although having completely different themes, this problem uses essentially the same idea as IMO 2003 P1. That exact idea is to prove that if we've already chosen $k$ members, then we can also choose the $(k+1)$-th member by showing that the number of forbidden members is less than that of total members, hence we can find at least one member not forbidden.