Your mistake is that by "state" you mean following: particle either in section A or section B. In reality what you use for computing entropy is number of ways for particle to be in some point of phase space, that is having particle coordinate and impulse (all 3D).

But you can omit these details. Consider box with single particle and 2 sections divided by barrier. Number of ways for this system to be is 1: particle is always on one side. Remove the divider and now you have two states: particle on the left _or_ particle on the right (each with probability 1/2). Entropy increased, because:

Before: $$\begin{align}S&=-k_b\sum_i p_i \ln(p_i)\\&=-k_b\times 1\times \ln(1)\\&=0\end{align}$$

After: $$\begin{align}S &= -k_b\sum_i p_i \ln(p_i)\\ &=-k_b(0.5\ln(0.5) + 0.5\ln(0.5))\\ &=-k_b\times (-0.7)\\&=0.7k_b>0\end{align}$$

Now, consider reversibility. It means that after entropy increased you will have to wait _very long time_ for system to come back to initial state. When your body dies, you need to wait really long to become alive again.

For number of particles it is much more probable that they will be distributed randomly across box's sections, rather than concentrated on one side. For 3 particles there are 2 options: either all on right, or all on left. But there are many more options (if all particles are distinguishable) for them to be around the box.