Here's the question I'm trying to solve:
Suppose that $n$ girls and $n$ boys are distributed around the outside of a circular table. Use mathematical
induction to prove that for any integer $n \geq 1$, given any such seating plan, it is always possible to find
a starting point so that if you travel around the table in a clockwise direction the number of girls you
pass is never less than the number of boys you have passed.
The proof seemed a bit trivial so I'm a bit doubtful on whether I did it right. Any help is appreciated. As some context, $\mathbb{N}^+$ is used to represent natural numbers starting at 1. Here's my proof to it:
let $n_g$ be the number of girls and $n_b$ be the number of boys
Prove $\forall n \in \mathbb{N}^+, n_g \geq n_b$
let $S(n)$ be $n_g \geq n_b$
Base Case ($n=1$):
$$ 1 \geq 1$$
$$True$$
Inductive Hypothesis:
let $k \in \mathbb{N}^+$, assume $S(k)$ holds, ie, that $k_g \geq k_b$
Inductive Step:
$$S(k+1) = k_g + 1 \geq k_b +1$$
$$ = k_g \geq k_b $$
therefore, $S(n)$ holds for all $ n \epsilon \mathbb{N}^+$
QED
Best Answer
You have misunderstood the question. You're not trying to prove the number of boys and girls are equal. You're trying to prove that no matter how they're arranged, you can select a starting point so that the number of girls you've passed (in the clockwise direction) is at least as great as the number of boys you've passed at every point in your journey.
Base case: $n=1$: If you start with the girl, then the number of girls that you have passed will always be at least as great as the number of boys you have passed.
Inductive step: Assume the hypothesis for $n=k$ and assume the circle has $k+1$ boys and $k+1$ girls. Start with any girl and proceed clockwise until you reach a boy. The first place where you reach a boy gives you a girl with a boy immediately next to her in the clockwise direction. Temporarily remove that girl-boy pair from the circle, yielding a shortened circle with $k$ boys and $k$ girls.
Now apply the inductive hypothesis to the shortened circle to select a starting point. By the inductive hypothesis, whenever you proceed clockwise around the shortened circle, you will always have passed at least as many girls as boys. Reinserting the removed pair doesn't change that result, because you've selected the pair so that you pass the removed girl before you pass the removed boy. Thus, the same starting point you picked for the shortened circle yields the result for the original circle. This proves the inductive step.