 Level: International Baccalaureate
 Subject: Maths
 Word count: 2849
There are n cards in a pile. The cards are numbered 1 to n and they in order with card n on the bottom of the pile and card 1 on the top. Problem: To move all the cards to another pile using the least number of moves.
Extracts from this document...
Introduction
Investigation: Cards (Algebra)
There are n cards in a pile. The cards are numbered 1 to n and they in order with card n on the bottom of the pile and card 1 on the top.
Problem: To move all the cards to another pile using the least number of moves.
Rules: 1) Only one card may be moved at a time.
 The card may only be placed on one of the 3 piles.
 A larger numbered card may not be placed on a smaller numbered card.
Objective: To find a formula which gives the minimum number of moves for the situation above for 3 piles. To find a formula which gives the minimum number of moves for 4 piles.
1) Investigation of Problem for 3 piles for small numbers, i.e. from n = 1 to n = 5.
n  Pile 1  Pile 2  Pile 3  No. of moves  Total no. of moves  
No. of card(s)  Card number(s)  No. of card(s)  Card number(s)  No. of card(s)  Card number(s)  
1  1  1  0    0      1 = 20 
0    1  1  0    1  
2  2  1,2  0    0      2 = 21 
0    1  1  1  2  2  
3  3  1,2,3  0    0      4 = 22 
1  3  1  1  1  2  2  
0    1  3  2  1,2  2  
4  4  1,2,3,4  0    0      8 = 23 
1  4  1  3  2  1,2  4  
2  1,4  2  2,3  0    2  
0    3  1,2,3  1  4  2  
5  5  1,2,3,4,5  0    0      16 = 24 
1  5  3  1,2,3  1  4  8  
2  2,5  1  3  2  1,4  2  
3  1,2,5  0    2  3,4  2  
1  5  1  1  3  2,3,4  2  
0    1  5  4  1,2,3,4  2 
Middle
5
1,2,3,4,5
1
6
1
7
2
0

5
1,2,3,4,5
1
8
2
6,7
2
9
9
1,2,3,4,5,6,7,8,9
0

0

0


21
1
9
5
1,2,3,4,5
1
8
2
6,7
17
2
6,9
5
1,2,3,4,5
2
7,8
0

2
0

5
1,2,3,4,5
3
6,7,8
1
9
2
10
10
1,2,3,4,5,6,7,8,9,10
0

0

0

0
n
Pile 1
Pile 2
Pile 3
Pile 4
No. of moves
Total no. of moves
No. of card(s)
Card number (s)
No. of card(s)
Card number (s)
No. of card(s)
Card number (s)
No. of card(s)
Card number (s)
10
4
7,8,9,10
3
1,2,3
1
6
2
4,5
9
25
5
4,7,8,9, 10
3
1,2,3
2
5,6
0

2
4
7,8,9,10
2
2,3
3
4,5,6
1
1
2
5
2,7,8,9, 10
0

4
3,4,5,6
1
1
2
4
7,8,9,10
0

6
1,2,3,4,5,6
0

2
2
9,10
1
7
6
1,2,3,4,5,6
1
8
2
1
10
1
9
6
1,2,3,4,5,6
2
7,8
2
2
7,10
2
8,9
6
1,2,3,4,5,6
0

2
0

3
7,8,9
6
1,2,3,4,5,6
1
10
2
Table 3
Table 3 shows the least number of moves required for the stated problem for 4 piles.
The table below shows the results found, in short.
n  (least) No. of moves  Difference in no. of moves 
1  1   
2  2  1 = 20 
3  3  1 = 20 
4  5  2 = 21 
5  7  2 = 21 
6  9  2 = 21 
7  13  4 = 22 
8  17  4 = 22 
9  21  4 = 22 
10  25  4 = 22 
Table 4
5) Formation of hypothesis for n = 11 to n = 15.
From the values found and shown in Table 4, a hypothesis can be made that for n = 11 to n = 15, there would be an increment of 23 = 8 each time.
Expected values are shown below, using Excel.
Table 5
6) Investigation of Problem for 4 piles for small numbers, i.e. from n = 11 to n = 15.
n  Pile 1  Pile 2  Pile 3  Pile 4  No. of moves  Total no. of moves  
No. of card(s)  Card number (s)  No. of card(s)  Card number (s)  No. of card(s)  Card number (s) 
Conclusion
n  Hypothesis  Actual 
11  33  33 
12  41  41 
13  49  49 
14  57  57 
15  65  65 
Table 7
7) Deriving of general statement for least number of moves for 4 piles.
Hypothesis is correct.
Therefore, the least number of moves, for the Problem, for 4 piles, increases by powers of 2 that are repeated 2 more than the power, for n that is greater than 1.
When n = 1, the least number of moves is 1.
When n = 2, the least number of moves is 1 + 1(20).
When n = 3, the least number of moves is 1 + 2( 20).
When n = 4, the least number of moves is 1 + 2( 20) + 1(21).
When n = 5, the least number of moves is 1 + 2( 20) + 2(21).
When n = 6, the least number of moves is 1 + 2( 20) + 3(21).
When n = 7, the least number of moves is 1 + 2( 20) + 3(21) + 1(22).
When n = 8, the least number of moves is 1 + 2( 20) + 3(21) + 2(22).
When n = 9, the least number of moves is 1 + 2( 20) + 3(21) + 3(22).
When n = 10, the least number of moves is 1 + 2( 20) + 3(21) + 4(22).
When n = 11, the least number of moves is 1 + 2( 20) + 3(21) + 4(22) + 1(23), so on and so forth.
The numbers that are not inside the brackets must always have a sum of n.
When n = 15, the least number of moves is 1 + 2( 20) + 3(21) + 4(22) + 5(23) = 65, as investigated.
8) Usage of general statement for 4 piles.
Using Excel, the predicted results for n = 16 to n = 25 are as follows.
Table 8
This student written piece of work is one of many that can be found in our International Baccalaureate Maths section.
Found what you're looking for?
 Start learning 29% faster today
 150,000+ documents available
 Just £6.99 a month