Problem

Source: Tournament of Towns,Spring 2002, Senior A Level, P4

Tags: counting, derangement, combinatorics proposed, combinatorics



The spectators are seated in a row with no empty places. Each is in a seat which does not match the spectator's ticket. An usher can order two spectators in adjacent seats to trade places unless one of them is already seated correctly. Is it true that from any initial arrangement, the spectators can be brought to their correct seats?