Let $G$ be a group with $n$ conjugacy classes. Prove there is a maximum $2^{n-1}$ normal subgroups. Let $G$ be a group with $n$ conjugacy classes.
Prove there is a maximum $2^{n-1}$ normal subgroups.
I know the cosets of normal subgroup $H$ with index $j$ has the form: $g_1H,g_2H,\cdots ,g_jH , g_i\in G$
In addition , I think if $\exists g\in G ,g^{-1}H_1g=H_2$, such that $H_1,H_2$ are normal subgroups so they have the same conjugacy classes.
I don't know how to approach the problem.
Any help is welcome,Thanks !
 A: Hint: every normal subgroup is the disjoint union of some of the conjugacy classes and the conjugacy class $\{1\}$ is always part of that.
A: If $n = 1$, then $G = \{e\}$ because no non-identity element is every conjugate to the identity element.  Thus, in this case, we see equality happens.  That is, the number of normal subgroups is equal to $2^{n-1}$.
Likewise, if $n=2$, then equality happens.  This is because if $n=2$, the group $G$ is non-trivial, and so it has $2 = 2^{2-1}$ normal subgroups: itself and the identity subgroup.
I claim that these are the only cases where equality is achieved.

Suppose $G$ is a group with $n$ conjugacy classes with $n\geq 3$.  Then it has fewer than $2^{n-1}$ normal subgroups.

Proof:  We prove it by contradiction.  So, assume $G$ is a group with $n\geq 3$ conjugacy classes and $2^{n-1}$ normal subgroups.  Since $n\geq 3$, we can find three distinct conjugacy classes.  Call them $A_0 =\{e\}$, $A_1$, and $A_2$.
From Nicky's answer, each of $H_1 = A_0\cup A_1$, $H_2 = A_0\cup A_2$, and $H_{12}=A_0\cup A_1\cup A_2$ must be a normal subgroup of $G$.  Choose $g_1\in A_1$ and $g_2\in A_2$.
Since $H_1$ is a subgroup of $G$ and $g_1\in H_1$, $g_1^{-1}\in H_1$.  But note that $g_1\neq e$, so $g_1^{-1}\neq e$, so $g_1^{-1} \in A_1$.  Analogously, $g_2^{-1}\in A_2$.
Since $H_{12}$ is a subgroup of $G$, $g_1 g_2\in H_{12}$.  Notice that $g_1g_2\notin A_1$, for if it was, then $g_2 = g_1^{-1}(g_1g_2)\in A_1$.  Likewise, $g_1g_2\notin A_2$.  Thus, we conclude $g_1g_2\in A_0 = \{e\}$.  In other words, $g_2 = g_1^{-1}$.  Thus $g_2\in A_2 \cap A_1$, giving a contradiction.  $\square$
So, if $n\geq 3 $ is the number of conjugacy classes of a group $G$, then the number of normal subgroups is at most $2^{n-1}-1$.  This bound can actually be achieved:  consider $G = D_6$, the dihedral group of order $6$.  This has $n=3$ conjugacy classes (the identity, the two non-trivial rotations, and all the reflections), and it has $2^{3-1} - 1 = 3$ normal subgroups: the trivial subgroup, the subgroup of all rotations, and the whole group.
On the other hand, not all groups with $n=3$ have $3$ normal subgroups: consider $\mathbb{Z}/3\mathbb{Z}$.
