• 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. 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

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

    simple observations and practical methods that have proved their value by successful use over a long period of time". (GendenkoB., SecklerB.) Also, it could be written as a quantitative measure of the degree of certainty of the observer or the relative frequency of occurrence of the even in a large

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

    It was necessary to see which were dependent and which were independent. This will show if there is relationship between no of book genres read and modal grade marks. Modal mark groups were made into below and above 61-80. This is because calculations made previously for girls and boys generally lay round 61-80.

  1. 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.

  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. 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 ...

    is ; therefore, if the fee to play is x and the payoff offered by the casino is 1.4x, the casino would just break even in the long term. Therefore, the payoff should be under 140% of the fee to play so that the casino stands to profit.

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