Intereting Posts

Monotonic Function Optimization on Convex Constraint Region
Lipschitz continuity of atomless measures
If $q^k n^2$ is an odd perfect number with Euler factor $q^k$, can $q = 73$ hold?
Prove that $ \lim\limits_{n \to \infty } \sum\limits_{k=1}^n f \left( \frac{k}{n^2} \right) = \frac 12 f'_d(0). $
Finite injective dimension of the residue field implies that the ring is regular
Showing that $ \displaystyle \lim_{n \rightarrow \infty} \left( 1 + \frac{r}{n} \right)^{n} = e^{r} $.
Represent Dirac distruibution as a combination of derivatives of continuous functions?
Given $n$ linear functionals $f_k(x_1,\dotsc,x_n) = \sum_{j=1}^n (k-j)x_j$, what is the dimension of the subspace they annihilate?
Burgers equation with initial data $u(x,0) = x^2$
Equivalent Cauchy sequences.
Combinations of multisets – the theory?
Quotient ring of a localization of a ring
Combinatorially prove that $\sum_{i=0}^n {n \choose i} 2^i = 3^n $
Taylor series for $\log(1+x)$ and its convergence
Main branches of mathematics

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.

- Inductive Proof that $k!<k^k$, for $k\geq 2$.
- Why is this 'Proof' by induction not valid?
- How can you prove $\frac{n(n+1)(2n+1)}{6}+(n+1)^2= \frac{(n+1)(n+2)(2n+3)}{6}$ without much effort?
- Proof by induction $\sum_{k=1}^{n}$ $k \binom{n}{k}$ $= n\cdot 2^{n-1}$ for each natural number $n$
- Fake induction proofs
- Need help with Knuth's proof for Gray Codes

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!

- Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves?
- Proof by Strong Induction for $a_k = 2~a_{k-1} + 3~a_{k-2}$
- Estimating partial sums $\sum_{n = 1}^m \frac{1}{\sqrt{n}}$
- Prove by mathematical induction that: $\forall n \in \mathbb{N}: 3^{n} > n^{3}$
- Strong Induction Base Case
- Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.
- Proof by induction - correct inductive step?
- A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$
- the concept of Mathematical Induction
- Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

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!

- Why does the graph of $e^{1/z}$ look like a dipole?
- Does there exist a function satisfying $\sup \int\vert u\vert=0$?
- When can you simplify the modulus? ($10^{5^{102}} \text{ mod } 35$)
- Rule C (Introduction to mathematical logic by Mendelson fifth edition)
- Proving Separation from Replacement
- Decay of a Convolution
- Prove analyticity by Morera's theorem
- What is a support function: $\sup_{z \in K} \langle z, x \rangle$?
- Find the square root of a matrix
- Semilocal commutative ring with two or three maximal ideals
- Scalar Product for Vector Space of Monomial Symmetric Functions
- counting triangles in a graph or its complement
- Can finite theory have only infinite models?
- Parabola in parametric form
- Limit of $h_n(x)=x^{1+\frac{1}{2n-1}}$