The first time I read about this problem, it was formulated in a way which made it clear that the host opens a door with a goat behind it. If you learn about it like this, you literally cannot believe how anyone (even Paul Erdős) could believe that switching is not better. After all, you choose a door with a goat behind it with probability 2/3 on your first try, and if you do this, than switching will always win you the car. It is so trivial that the only "paradox" here is that it is classified as a paradox.
E: the explanation on Wikipedia is unnecessarily elaborate and hard to follow:
"The given probabilities depend on specific assumptions about how the host and contestant choose their doors. A key insight is that, under these standard conditions, there is more information about doors 2 and 3 that was not available at the beginning of the game, when door 1 was chosen by the player: the host's deliberate action adds value to the door he did not choose to eliminate, but not to the one chosen by the contestant originally. Another insight is that switching doors is a different action than choosing between the two remaining doors at random, as the first action uses the previous information and the latter does not. Other possible behaviors than the one described can reveal different additional information, or none at all, and yield different probabilities. "
What?
I only took a single class of statistics at university, but my biggest take-away from that class is that you absolutely cannot trust your gut, because the human bias is crazy strong.
Humans naturally over-connect. We see causation where only correlation is present. Gamblers believe that something random that has happened frequently (like roulette landing on a specific number) is more likely to happen again. Educated people learn about dependent and independent probability, which corrects this impulse. But sometimes it over-corrects.
The Monty Hall problem is hard because people see can't explain the dependent probability link clearly and conclude that the probabilities are independent and their brain is acting up - first guess 1 in 3, second guess 1 in 2. After all, the game host is always capable of opening a door with a goat, and the player doesn't know anything. Put differently, what did the player learn between the first and the second guess that should make the player now believe one door is more likely than the other of the remaining two?
It also takes advantage of our natural thinking. The problem is artificial, because, outside of a game show, the host could also just not offer to switch. Emotional then, brains consider the information that the host made the second offer even if it's not logically part of the problem.
If the problem does not state what the host's algorithm is, and you have no knowledge of the host's algorithm (example: you have never seen the TV show before), then the logical action is to assume the host chooses a door to reveal randomly.
Isn't it the other way round?
The only scenario in which the host doesn't give you any useful information by opening a door is when the host chooses the door at random. Assuming the host didn't choose the door with the prize, your odds are 50:50.
Of course all of this hinges on you being aware of the host's decision making paradigm, and that you want a car more than you want a goat.
The paradox disappears when you think about probability as a tool for reasoning from incomplete information, not as anything to do with "physical" property of the system under investigation. It then makes perfect sense that after receiving new information from the host we should reassign our probabilities.
"You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat." Where does it state that the host always opens a door with a goat? From the statement it looks like the goat was accidental. No wonder Paul Erdős got confused by this too. The translation of the paradox to his language could have been even more confusing.