Question 287851: Ten pennies and ten nickels were arranged alternatively as PNPN...PN. A move consists of exchanging the position of two adjacent coins. What is the minimum number of moves needed to move all the pennies to one end,and all the nickels to the other end,i.e.,PPP...PN...NNN?
A 10 B 20 C 25 D 40 E 45
Answer by drk(1908)   (Show Source):
You can put this solution on YOUR website! To understand this question it is helpful to look at smaller cases:
2 coins: pn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .0 moves
--------
3 coins:pnp -> ppn . . . . . . . . . . . . . . . . . . . . . . . 1 move
4 coins:pnpn -> ppnn. . . . . . . . . . . . . . . . . . . . . . 1 move
--------
5 coins:pnpnp -> ppnnp -> ppnpn -> pppnn . . . 3 moves
6 coins:pnpnpn . . . . . . . . . . . . . . . . . . . . . . . . . . .3 moves
--------
7 coins: pnpnpnp. . . . . . . . . . . . . . . . . . . . . . . . . . 6 moves
8 coins: pnpnpnpn. . . . . . . . . . . . . . . . . . . . . . . . . 6 moves
--------
9 coins: pnpnpnpnp. . . . . . . . . . . . . . . . . . . . . . . . .10 moves
10 coins: pnpnpnpnpn. . . . . . . . . . . . . . . . . . . . . . .10 moves
-----
Notice that the number of moves for each pair after the first will be triangular in nature: 0, 1,3,6,10 and so on.
So, 10 pennies will have 10 moves; ( A )
|
|
|
