A boy has a secret. He goes to a meeting with other kids where there are $n\geq{2}$ people, including himself. A girl (the president) claims that each of the $n$ people in the meeting is friends with at least $\frac{n}{2}$ of the other kids. Each of these friendships is mutual (i.e. Person A is friends with Person B, then Person B is friends with Person A). The boy then tells all of his friends about his secret; these friends tell all of their friends, and so on. Prove that all $n$ kids will know the boy's secret.
What I have:
I think we will have to prove this by induction.
Base case: $n = 2$, the boy tells the president and everyone knows his secret.
Induction Hypothesis: Assume claim is true for $n=k$, where there are $k\geq{2}$ people and each kid is friends with at least $\frac{k}{2}$ people.
Induction Step: prove $n = k +1$. There are $k+1$ kids and each $k$ kid is friends with at least $\frac{k+1}{2}$ people. If we were to remove any kid (besides the boy), then by induction hypo. the claim is true. But I'm stuck on what to do from here if the correct technique is to use induction.
Suppose at least one kid won't know the secret, call him $Z$. That is to say, he can't be reached by a chain of friends, from the kid who has the secret (call him $A$).
But then none of $Z$'s friends will know the secret either. There are at least $n/2$ such friends, plus $Z$. Which means at least $\lfloor n/2\rfloor+1$ kids won't know the secret.
On the other hand, the boy with the secret ($A$) has at least $n/2$ friends, so together with himself, at least $\lfloor n/2\rfloor+1$ kids will know the secret.
But $2\lfloor n/2\rfloor+2$ is always greater than $n$: contradiction.
Side comment: the result proved here is slightly stronger than what is assumed in the question. When $n$ is odd, if a kid has at least $n/2$ friends, then he has at least $\lceil n/2\rceil$ friends (the number of friends, which is an integer, is $\ge n/2$). But we need only $\lfloor n/2\rfloor$ of them.