Let $G$ be a finite group. Show that there exists a generating set $S$ of $G$ with $|S| \le \log_2 |G|$.
I started looking what can I get if I look at generating sets of elements of $G$,i.e., $<x_1>,<x_1,x_2>,<x_1,x_2,x_3>...$ and yet I'm not sure how can I limit it as required.
Any other ideas?
Basic idea: simply pick elements successively so that the next one is not in the generated subgroup of the elements you already picked. In each step, the size of the generated subgroup at least doubles. This solves the problem with $n$ elements where $n$ is the upper floor of $\log_2 |G|$. To improve this, we break the problem to two cases.
Case 1: If every element has order 2 or 3 in $G$. Then by Cauchy's theorem, $|G|= 2^k3^m$. By Burnside's theorem, $G$ is solvable:
https://en.wikipedia.org/wiki/Burnside_theorem
So there is a sequence of groups, each an extension of the previous one by $\mathbb{Z}_2$ or $\mathbb{Z}_3$. Thus we can pick the new elements successively so that in the i-th step we generate the i-th subgroup in the chain. This requires $k+m$ elements, which is clearly strictly less than $\log_2 |G|$.
Case 2: There is an element $g$ whose order is at least 4. Then start by this. So now instead of having the lower estimation for the size of the i-th subgroup $2^i$ (see the basic idea), we have $2^{i+1}$, as the first generated subgroup has size at least $4=2^2$. This is just enough, the number of elements is at most the upper floor of $\log_2 |G|$ minus 1 now.