Intereting Posts

Why is the cardinality of irrational numbers greater than rational numbers?
The cone of a topological space is contractible and simply connected
Substitution $x=\sinh(\theta)$ and $y=\cosh(\theta)$ to $(1+x^{2})y'-2xy=(1+x^{2})^{2}$?
Not sure how to go about solving this integral
The Convergence of an alternating series test
Conformal mapping circle onto square (and back)
What is the solution to Nash's problem presented in “A Beautiful Mind”?
How to show $\ell^2_p$ not isometric to $\ell^2_{p'}$ unless $p\in\{1,2,\infty\}$?
Dual space and covectors: force, work and energy
Why study Algebraic Geometry?
Why is $L^{1}(G)$ unital if and only if $G$ is discrete?
$e$ is the only number in the universe having this property?
Why doesn't Hom commute with taking stalks?
Show that an infinite number of triangles can be inscribed in either of the parabolas $y^2=4ax$ and $x^2=4by$ whose sides touch the other parabola.
Product of perfectly-$T_2$ spaces

title can’t exactly capture the description of this problem so well. Here’s the question in full:

“At a convention, any group of four people contains one who knows the other three. Prove there is someone at the convention who knows everyone else.”

I’ve tried to prove this inductively, but am not sure whether or not that is the correct way to go about it.

- Explaining why proof by induction works
- Prove $(n^5-n)$ is divisible by 5 by induction.
- Prove $n^2 > (n+1)$ for all integers $n \geq 2$
- Prove $3^n \ge n^3$ by induction
- The sum of odd powered complex numbers equals zero implies they cancel each other in pairs
- Prove by mathematical induction that $2n ≤ 2^n$, for all integer $n≥1$?

Induction Hypothesis: Assume that there is someone at the convention who knows everyone else, given that any group of four people contains one who knows the other three (assume this is true given $n$ people).

Basis case: there are four people at the convention. Therefore, there is one in this group of four who knows the other three (everyone else at the convention).

Induction step: Prove this is true for $n+1$ people. We see that this is the same as inserting one more person into a convention with $n$ people, where there must be someone who knows everyone. Therefore, we only need to show that this person who knows everyone also knows the $n+1$th person we’re inserting. And I’m stuck.

If anyone could help me out here, that would be greatly appreciated. Thanks!

- Can't find the demonstration of a theorem about recursion
- Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.
- Prove by induction that $5^n - 1$ is divisible by $4$.
- Proof for power functions
- Proving the total number of subsets of S is equal to $2^n$
- Induction proof (bitstring length)
- Proving by induction that $1^3 + 2^3 + 3^3 + \ldots + n^3 = \left^2$
- Odd Binomial Coefficients?
- Induction, 0'1 and 1's sequence fun question
- Fascinating induction problem with numerous interpretations

I will assume that knowing someone is symmetric, i.e. if person X knows Y then Y knows X.

Lets call the $n+1$-th person B. Before B joined someone must have known everyone at the convention, call her A. Now suppose that A doesn’t know B and that the convention still has the property that in all groups of 4 there is someone who knows the others. Then we have to show that there is someone else at the convention who knows everyone else.

For any pair of people C and D that aren’t A or B we know that either C or D must know all of the others in the group ABCD. In both cases C and D know each other. This shows that any person that isn’t A or B knows all other people that aren’t A or B. Now pick a specific pair of such people one of them must also know A and B and so he knows everyone at the convention!

This is a way to do it without induction.

Choose any person, say $A$. First, we claim that $A$ knows everyone, except possibly for $2$ people. Suppose that there are three people that $A$ does not know, say $B$, $C$, and $D$. Then the quadruple $\{A,B,C,D\}$ violates the given condition, so the number of people that $A$ does not know is at most $2$.

If $A$ knows everyone, then we are done. If $A$ does not know some person, then call this person $B$.Let $C$ and $D$ be two people other than $A$ or $B$. Then in the quadruple $\{A,B,C,D\}$, the person who knows everyone else in the quadruple cannot be $A$ or $B$, so it must either be $C$ of $D$; in particular, $C$ and $D$ always know each other. This tells us two things. First, since $C$ and $D$ were chosen arbitrarily, every pair of people, not including $A$ or $B$, knows each other. Second, one of $C$ or $D$ must know both $A$ and $B$. Therefore, one of $C$ or $D$ knows everyone.

Thus, we are done!

- Do we need net refinements not induced by preorder morphisms?
- Is a trigonometric function applied to a rational multiple of $\pi$ always algebraic?
- Surjective Maps and right cancellation
- Verifying Ito isometry for simple stochastic processes
- Upper bound for complex polynomial
- For closed subsets $A,B \subseteq X$ with $X = A \cup B$ show that $f \colon X \to Y$ is continuous iff $f|_A$ and $f|_B$ are continuous.
- Showing that $ \int_{0}^{1} \frac{x-1}{\ln(x)} \mathrm dx=\ln2 $
- How can this be proved $\lim_{x\to\infty}(f(x)+f'(x))=l$
- Advice on self study of category theory
- Does smashing always increase the connectivity of a space?
- What is the difference between minimum and infimum?
- Annihilator of a simple module
- For $G$ a group and $H\unlhd G$, then $G$ is solvable iff $H$ and $G/H$ are solvable?
- Do factorials really grow faster than exponential functions?
- Stronger than ZF, weaker than ZFC