Problem #PRU-64849

Problems Methods Pigeonhole principle Pigeonhole principle (other)

Problem

On a ring road at regular intervals there are 25 posts, each with a policeman. The police are numbered in some order from 1 to 25. It is required that they cross the road so that there is a policeman on each post, but so that number 2 was clockwise behind number 1, number 3 was clockwise behind number 2, and so on. Prove that if you organised the transition so that the total distance travelled was the smallest, then one of the policemen will remain at his original post.