1) let's use 2 different colors to color every body in such a way that people who don't know each other get different colors since k is odd, obviously there is a minority color, the number of minority is at most n. Take a n persons group that includes all minority persons, this group doesn't satisfy the condition given in the description. therefore such a coloring is not possible which means at least 1 person knows all other persons 2) use the same coloring approach so that there are n+1 person for each color, make everybody know all others except for 1 person in the opposite color group

The above is quite cryptic, lacking argumentation, and in fact starting altogether wrong: what if there are $3$ people, pairwise not knowing each other? how are we assigning those two colors? But I will present a proof based on the underlying lines of the above. 1) Model the situation by a graph $G$ on $k=2n+1$ vertices (the people), where edges are between people not knowing each other. Assume there exist such graphs without an isolated vertex (a person that knows all others). Among those graphs, pick a graph $H$ with minimal number of edges. Then this graph is acyclic, otherwise we can remove an edge $e$ belonging to a cycle; this does not influence the conditions, so $H - e$ is again one of these graphs, and has less edges. So $H$ is a forest (a union of disjoint trees). Now we can color the vertices of each tree with two colors, so that neighbouring vertices bear different colors (easy to see the chromatic number of a forest is $2$). One of the colors will have been used at most $n$ times. Take a set of $n$ vertices including all these; then the conditions say there exists a $(n+1)$-th vertex not connected to any of them. This vertex must be of the other color, but this is a contradiction, since each vertex of a color must be connected with (at least) a vertex of the second color. 2). A model is easily given by the graph on $k=2n+2$ vertices and edges between vertices $j$ and $j+n+1$, for all $1\leq j \leq n+1$. Now for any set of $n$ vertices, them together with those paired with them are at most $2n$, so there exist at least two other vertices with no edges connecting them with any vertex from the set of $n$. Any of them is therefore a person knowing all those $n$, and clearly no-one knows everybody else.

Nice to know that we think alike, mavropnevma.

In fact, point 1) of the problem is a direct consequence of the following Theorem. The vertices of a finite simple graph $G$ with no isolated vertices can be partitioned into two non-empty classes, such that each vertex from any class is connected by an edge to at least one vertex from the other class. Proof. 1. Induction. Consider the subgraph $G'$ made by a vertex $v$ and all its degree $1$ neighbours (if any). This is a star graph, for which we can easily find the two classes; one is made by the center $v$ of the star, the other is made by the ends of the spikes. Since $G-G'$ has less vertices, it can be partitioned, and then we can just put together classes from the two subgraphs. If $G'= G$, we have proved it can be partitioned. If $G'= \{v\}$, we just add $v$ to a class of $G-G'$ so that it has an edge towards the other class. 2. Infinite descent (extremal element). Make an arbitrary partition. If a vertex has no edge connecting it to the other class, move it there. This decreases the number of such vertices, so we must reach zero. Alternatively, start with an extremal partition, having least number of such vertices; then since we could decrease their number as described, their number is in fact zero. 3. Trees. Each (connected) component has a spanning tree. Partition the vertices of each such tree into two classes, by the parity of their distance to a root of the tree. The model for part 2) described above is in fact a $1$-factor (perfect matching) bipartite graph with two classes of $n+1$ vertices each.

Quote: what if there are 3 people, pairwise not knowing each other? how are we assigning those two colors? If no coloring approach is possible then the proof is automatically given if this is too "cryptic", then there's another "constructive" one with completely different approach: Pick any n persons, there is a (n+1)th person A who knows each of these selected n persons. This A along with any other arbitrary person B in the selected n, mutually know each other. pick A and B, Arbitrarily add n - 2 persons to form a new n persons group, there is a new (n+1)th person C who know these group, therefore, A,B,C mutually know each other Continue this process until we have a group with n persons, and there is, again, a (n+1)th person who knows this group, so together we are able to have a group of n+1 persons who mutually know each other Since there are only 2n+1 persons in total, now for the rest n persons, the (n+1)th person X who knows them all is in the group we just formed, therefore this X knows everybody else This is simply about finding a clique in a particular graph

galaas wrote: let's use 2 different colors to color every body in such a way that people who don't know each other get different colors... As I said, this cannot be done, for example when three people mutually don't know each other. All I've done was to use your coloring idea and produce a complete proof, as testified by the following quote. mavropnevma wrote: But I will present a proof based on the underlying lines of the above.

On a different line, let us notice that those numbers $k=2n+1$ and $k=2n+2$ are threshold numbers. This is because if a set of $k$ people has that property about $n$-subgroups, there exists a set of $k+1$ with the same property, and with the extra person not knowing everybody else. An example goes like that; add a person $x$ knowing everybody else but some person $a$. For any $n$-subgroup without $x$, the property trivially holds, while for an $n$-subgroup $S$ containing $x$, there is a person $y$ knowing all of $(S \setminus \{x\}) \cup \{a\}$, hence $y$ will know all of $S$ too (since $y$ knows $x$).

The first part is a well-known Russian problem. See here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1931292&sid=60e145297ac92e157048ed50a17221e0#p1931292