Noticing confusion in physics

Before going into why the real answer is what it is, there is a flaw in your reasoning for your original answer. Your reasoning about density assumes the gas is free to expand and contract, which is not an assumption given in the problem. An ideal gas in a box of fixed size does not gain or lose mass or volume when heat or cooled, only T and P change. And the speed of sound in air does not change if you measure it inside with the doors and windows closed and sealed. So what variables can we rule out?

If I make the room bigger or smaller while holding T and P constant, v(sound) does not change. If it did, it would be very obvious in daily life.

If I increase pressure while holding V and T constant, I do it by adding more gas molecules. This increases density, but does not change the velocity of the gas molecules. In this scenario, your answer is correct. Speed of sound varies with P. However, this is only true because real gases are not ideal gases, and there are more complex interactions between molecules. In an ideal gas where all the interactions are perfectly elastic and instantaneous collisions, the density has no effect because mean free path is irrelevant to instantaneous or average speed of movement across the group of molecules as a whole, it just changes which molecules are moving. Side note: Remember sound is a pressure wave. So, if this were not true, then the speed of sound would depend on how loud it is. Also, it would be different at the peak and trough of each cycle of the pressure wave. Again, in real gases there are effects of this kind, and there is a maximum volume sound can be (in air at sea level, around 194 decibels the pressure at the trough hits zero; this is a shockwave and it can move faster than sound). But ideal gases assume all that away.

If we increase or decrease the amount of gas at fixed T, then either we're just adding volume again, or we're just increasing pressure again, and we've seen that those shouldn't have an effect on an ideal gas' speed of sound.

So now let's increase T. It doesn't matter what effect this has on P and V and n, as seen in the above. So what's left? Increasing T linearly increases the average kinetic energy of the gas molecules (PV and NkT both have units of energy, this is why), and velocity increases as the sqrt of kinetic energy. So if gas molecule velocity is what determines v(sound), then it has to be that v(sound) increases as sqrt(T).

I'm not sure what level physics class you're in, but I have two very general pieces of advice. 

The first is that you can often get very far by figuring out what doesn't or can't matter, and what has to be held constant. This is why conservation laws are so important! It's also why boundary conditions of a problem are important. They let you write down equations that constrain what the solution can possibly depend on. As an example, a string attached to fixed points on both ends can only vibrate at frequencies where those ends don't move. Air vibrating in a tube that's closed at one end can't have net motion at the closed end, but has to be moving at the other end for any sound to come out at all. These kinds of considerations let you figure out what resonance frequencies are possible in principle for idealized versions of different types of musical instruments. (If you get to more advanced physics, this is why there's so much discussion of symmetry. Noether's theorem tells us that every symmetry of the laws of physics implies a conservation law, and vice versa. "Energy is conserved" is equivalent to saying "The laws of physics don't change over time." "Linear and angular momentum are conserved" is equivalent to saying "the laws of physics don't depend on where you are or what direction you're facing." There's a reason Einstein originally wanted Relativity to be called "The Theory of Invariants": he arrived at it in large part by thinking about what couldn't matter and what couldn't change, then letting everything else vary however it needed to in order to accommodate that.)

The second is something a professor used to like to say: that if you really want an intuition for physics you need to feel it in your bones. Try things out. Look for places in your regular life where different concepts could apply, and try to reason out how they apply. It's a slow process that doesn't always match up to a semester-long class schedule, but it's the kind of thing where a year or two later you'll find yourself saying, "Oh yeah, that's what they meant!" Sometimes this takes a long time and a lot more physics than you'd expect! I was in grad school for materials science when one professor wrote down an equation at the end of a handful of math-heavy lectures and said, "And that's why metals are shiny." Other times it turns out you can explain seemingly complicated things with high school physics and very careful reasoning.

Here's a handwavy attempt from another angle:

Suppose you have a container of gas and you can somehow run time at 2x speed in that container. It would be obvious that from an external observer's point of view (where time is running at 1x speed) that sound would appear to travel 2x as fast from one end of the container to the other. But to the external observer, running time at 2x speed is indistinguishable from doubling the velocity of each gas molecule at 1x speed. So increasing the velocity of molecules (and therefore the temperature) should cause sound to travel faster.

(Also, for more questions like this, see this post on Thinking Physics) [LW · GW]

We've been thinking about explanations in our research (see, e.g., https://arxiv.org/abs/2205.07938) and your example of explaining the wrong answer well is lovely.

I dislike these kinds of questions, because they're usually posed at a point well before the wave equations are presented. At this point, you are largely working with verbal explanations and, as you point out, verbal explanations are much harder to pin down. 

Mathematically, if A implies B, and you are working to the best of your ability, you can't derive ~B (you may not be able to derive B, of course!) Verbally, this is not so clear; a lot of philosophy is people arguing about whether A implies B or ~B.

If the underlying logic is (as it is in physics) mathematical, then a verbal account of mathematical fact A can be loose enough that you can derive ~B, because the verbal account is also consistent with A', which implies ~B.

In these explanations, there's another factor: a lot of the talk is relying on intuitions for "ordinary solids". One explanation I encountered when I googled referred to the "stiffness" of a hotter gas. While you might be able to cash this out in more formal terms, the temptation is to think about stiffness in one's normal experience. (It might have been possible to get the right answer by imagining heating up a bicycle tire that's already inflated; intuitively, the casing will be stiffer, "ring" at a higher frequency, etc.)

If you continue on in physics to relativity, quantum mechanics, etc, you end up dropping this kind of talk very quickly. This is why I don't like these questions; it's a bit useless to get good at them, because the more advanced you get the more you learn to rely on mathematical intuitions to get the right answer (and then perhaps informal folk talk afterwards, if you communicate to a popular audience.)

My thought after reading the first sentence of your post, and before reading any of the comments, was that gases become less compressible at higher temperatures, which should make it more responsive to a pressure-wave, raising the speed of sound in that medium.

I think the confusion is about unverified assumptions. The author assumed that the problem is about an open or a leaky space (perhaps thinking about the sound traveling across the quad in the summer vs winter), while the teacher meant some closed container (e.g., a pressure cooker). The teacher wins. 

You're making assumptions beyond the problem statement.  The problem never says pressure is constant, so a temperature change does not imply a change in volume.  (An inferred change in particle number could also change the density, but I'm guessing that wasn't your mistake.)

At this point, I'm thinking that a decrease in density does not decrease the speed of sound in gases, only in liquids and solids.

Actually, a decrease in density increases speed of sound in liquids and solids.  (intuition: less mass -> less inertia, faster movement for same forces). The same also does apply to gases (depending on what else is held constant, but consider, e.g. helium).

And, in the case of a gas, it's not clear to me that, other things being equal, moving farther before hitting another particle should be expected to decrease the speed of sound. After all, even if it takes a longer time for a particle to hit another particle, it's traveling farther in that time, so the total distance per time isn't dropping. 

Here is my synthesis of what happened: in solids and liquids, density does affect the speed of sound, but in gases, a third factor is pressure. If you increase the temperature, density can increase, but pressure also increases by a portional amount since the molecules are hitting harder. These two changes cancel out. Thus, in a gas $v\propto \sqrt{T}$ only.

It's confusing to me here what you are assumptions you are making about what else is happening as the temperature changes. E.g. mentioning both pressure and density changing rules out both constant pressure and constant volume. Also, you mention density increasing instead of  decreasing, which might be a typo?

One potential way to think about it, if you want to think in terms of pressure and density: (for actual math, see e.g. https://en.wikipedia.org/wiki/Bulk_modulus)

Constant volume case: as the temperature increases, the density stays the same but the forces increase due to the increase in pressure, so sound moves faster.

Constant pressure case: as the temperature increases, the forces stay the same (since we're holding the pressure constant), but the density (and hence inertia) decreases, so sound moves faster.

Good for you to be thinking about improving your understanding, best of luck in building up a strong physical intuition.

If you increase the temperature, density can increase, but pressure also increases by a portional amount since the molecules are hitting harder. These two changes cancel out.

I think you meant to say "density can decrease" not "increase"?