IMO Shortlist 1994 problem C4
Kvaliteta:
Avg: 0,0Težina:
Avg: 7,0 There are
cells in a row labeled from
to
and
cards labeled from
to
. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card
into cell
for each
. The allowed move is to find the smallest
such that cell
has a card with a label
, pick up that card, slide the cards in cells
,
, ... ,
one cell to the left and to place card
in cell
. Show that at most
moves are required to get every card into the correct cell and that there is a unique starting position which requires
moves. [For example, if $n = 2$ and the initial position is 210, then we get 102, then 012, a total of 2 moves.]
![n + 1](/media/m/3/6/d/36dc98984132471cc8b030d766fd893a.png)
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n + 1](/media/m/3/6/d/36dc98984132471cc8b030d766fd893a.png)
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![h](/media/m/e/4/3/e438ac862510e579cf5cbdbe5904d4ba.png)
![h](/media/m/e/4/3/e438ac862510e579cf5cbdbe5904d4ba.png)
![k > h](/media/m/5/c/c/5cce0e7a73eed4c5a5b3987f8a5425ef.png)
![h + 1](/media/m/e/7/f/e7f1af3edc2ea55026105b56e80e1f7d.png)
![h + 2](/media/m/1/4/6/146c28f0100d356e6ef6397f65a5c639.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![2^n - 1](/media/m/3/6/8/368d10e8ec7984984aeaca1729252368.png)
![2^n - 1](/media/m/3/6/8/368d10e8ec7984984aeaca1729252368.png)
Izvor: Međunarodna matematička olimpijada, shortlist 1994