Solution to Problem 134


Congratulations to this week's winner

Michael McLaughlin

Further solutions were submitted by Joe Thornton, Eric Baldwin, Courtney Pelowski, Sean Koors.  Further solutions were submitted by Alumnus Andrew Quigg, and from Lou Cairoli, Sudipta Das, Dane Brooke, Burkart Venzke, Al Zimmermann, Nancy Schwarzkopf, Scott Powell, Bryan Fluher, Philippe Fondanaiche, and an anonymous solver.


Let's write the ordered pair (m,w) to designate the number of men to the left of the empty seat and the number of women to the right of the empty seat.  So we are starting with the ordered pair (10,10) and we wish to end at the ordered pair (0,0).  Each "slide" move correponds to either (m,w)®(m-1,w), if a man slides to the right, or to (m,w) ®(m,w-1), if a woman slides to the left.  A "jump" move corresponds to (m,w)®(m-1,w+1), if a man steps to the right over a woman, or to (m,w)®(m+1,w-1), if a woman steps to the left over a man.  A solution to the problem is shown in the sketch on the left, where the vertices represent the ordered pair (m,w) with (10,10) in the upper right corner.  This solution uses 220 = 112- 1 moves.  It cannot be done with fewer moves!  (Can you prove this?)

In general, the minimal number of solutions of n men and n women is (n+1)2 - 1 with the pattern shown in the sketch generalizing to the realize this minimum.

A question for further thought:  Suppose there are an unequal number of men and women, say initially you have m men and w women with m ¹ w. Now what is the minimal number of moves required for a switch, and how is this switch achieved?

You are visitor number 2706 to this page.