Already in a derangement
Source: Tournament of Towns,Spring 2002, Senior A Level, P4
May 14, 2014
countingderangementcombinatorics proposedcombinatorics
Problem Statement
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?