Why does increasing the volume in which a gas can move increase its entropy? Let's say we have a box with a non-permeable wall separating the box in half. There is gas on the other side of the wall. Now we remove the wall so that the gas can diffuse to the other half of the box.

It is said that the entropy of the gas increases because the molecules now have more room to move, and therefore there are more states that the gas can be in. I can understand this well.
But the change in entropy is also defined as follows:
$\displaystyle \Delta S = \frac{Q}{T}$
Where $T$ is the temperature of the gas and $Q$ is the change in heat of the system. But if we look at this definition, why did the entropy change for the gas inside the box? By just removing the wall, the kinetic energy of the molecules does not change, therefore the temperature does not either. We also didn't add any heat to the system, so $Q$ is zero as well. So why did the entropy change?
 A: This is a classic example of making sure you know what your equations actually mean. You are thinking along the lines of
$$Q=T\Delta S$$
Where your change in entropy determines the heat exchange. This is not the right way to view the equation.
The actual meaning of the equation is "if you have reversible heat flow $Q$ at temperature $T$ for a reversible process, then you have a change in entropy $\Delta S$". Since there is no heat flow, this equation does not tell you anything useful. All you can say is there is no entropy change due to a heat flow.
A: The formula you used, $$\mathrm{d} S=\frac{\mathrm{d}Q_{\mathrm{reversible}}}{T}$$is a simplification for situations where all other factors are constant. Here, you're better off using $$\Delta S=nR\ln\frac{V_2}{V_1}$$
($R$ is the gas constant, and $n$ is the number of moles) It's a more sensible formula since the only thing you're changing is volume: the temperature and energy are both maintained as constants.
Eventually, the entropy did change, but the formula you used wasn't the right one, and hence it suggested that entropy wouldn't change.

The Wikipedia page on entropy has a list of useful formulas, you'll need to choose the appropriate one for different situations, depending on what factors you're maintaining as constants.
A: A statistical mechanics perspective. The phase space of an atom in the gas is described by the microstates, made from position and momentum values, $(x, y, z, p_x, p_y, p_z)$.
The allowed position states are constrained by the dimensions (l, w and d) of the box, $0<x<l$, $0<y<w$, $0<z<d$.
When you increase the box size, you have increased $W$, the number of microstates and therefore increased the entropy of the gas, according to the Boltzmann entropy definition, 
$S=k_B \ln W$
A: All previous answers get close. The definition of $S$ in thermodynamics (the statistical mechanics view is more straightforward in this case, but this was not the question) is:
$$dS = dQ_{rev} / T$$
which means that the infinitesimal change in entropy going from state A to state B is tantamount to the heat $dQ$ exchanged along any reversible transformation going from state A to state B, divided by the temperature $T$ at which this happens.
Since in this case we are going to a final state which has the same temperature as before, like you said, it is smart to directly use an isotherm curve from $V1$ to $V2$. Now, in an isotherm going from $V1$ to $V2$ the heat exchanged is: $$\Delta Q_{rev}=nRTln(V2/V1)$$ where $R$ is the gas constant (see wikipedia for derivation if this is not clear) so that in our case, integrating $dS$
$$ \Delta S=\Delta Q_{rev}/T = nRln(V2/V1)$$ which is the formula Chair used - but it is not a magical formula, it comes from your definition. Your definition is NOT a simplification (you wrote the integrated version, the right one is the "differential" one, but whatever), it is the right definition!
The tricky point is that $Q$ is not the heat of your process, but the heat of $any$ process starting and ending in the same states you have. Then you just need to find a smart way to compute it.
More in general, since you can always reach two points of the PV diagram with two transformation, an isothermal one and a constant-volume one, you can always write the entropy of a perfect gas going from A to B as:
$$n C_v ln(TB/TA)+nRln(VB/VA)$$ where $C_v$ is the specific heat of the gas at constant volume. This formula is again a general formula (amongst many others for the perfect gas) but it can be easily derived from your definition!
The entropy change does not depend on the actual heat exchanged in the transformation, it comes from the simple fact that you are changing state. However, to compute it, we use the heat along a different path. That is all!
