• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

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.

  1. The card may only be placed on one of the 3 piles.
  2. 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

...read more.

Middle

8

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.

image01.png

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)

...read more.

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.

image02.png

Table 8

...read more.

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

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related International Baccalaureate Maths essays

  1. Mathematics (EE): Alhazen's Problem

    once off the edge and strike another ball at a second given point.4 The focus question of this extended essay will be: Heinrich D�rrie also described the problem as "find in a given circle an isosceles triangle whose legs pass through two given points inside the circle".

  2. This essay will examine theoretical and experimental probability in relation to the Korean card ...

    Nan-Cho, June is Mo- Ran, July is Hong-Ssa-Ri, August is Gong-San, September is Kook-Jun, October is Dan-Feng, November is Oh-Dong and December is Bi. This game "Sut-Da" does not use all these 48 cards but only uses 20 cards. This game can hold two to ten people in one game,

  1. How many pieces? In this study, the maximum number of parts obtained by n ...

    Relationship between maximum number of regions (R) and number of chords (n) using technology: 1. 2. 3. Conjecture for maximum number of regions (R) and number of chords (n): R = (1/2)n 2 + (1/2)n + 1 n = 1--> R = 2, n = 2--> R = 4, n

  2. math work 1

    * Halle los valores de x2 - x1 y de x4 - x3 y denomine a estos valores SL y SR respectivamente. * Finalmente, calcule D = Para poder trabajar con las intersecciones de la gr�fica, debo definir que es.

  1. Statistics project. Comparing and analyzing the correlation of the number of novels read per ...

    Number of books Frequency Fx 1 6 6 2 8 16 3 6 18 4 3 12 5 1 5 6 2 12 Total 26 69 \ Mean==?fx = 69 N 26 Mode: 2, which shows that most girls preferred a lower amount of books to read Median: 3.5th value: 1.

  2. Networks - Konigsberg Bridge Problem.

    After you fill in the table, we are left to find a pattern in the table and the importance of even and odd nodes are very essential at that stage. Then in the second part, we test out our rule or check if we have to start with an even or odd node.

  1. matrix power

    However, for a matrix to be able to be raised to the power the matrix must be a square matrix, meaning that it must be orthogonal in shape and contains the same width and height all around. The following list describes the effects on a matrix when a matrix is

  2. The purpose of this investigation is to create and model a dice-based casino game ...

    In order to determine the probability that player A wins, it is necessary to first find the probabilities of the outcomes of each of player A?s rolls. Now consider a specific whole number p between one and six inclusive. In order for p to be recognized as player A?s higher

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work