• 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. How many pieces? In this study, the maximum number of parts obtained by n ...

    Split (k + 1) into (k + 1/2 + 1/2) --> (1/2)k 2 + (1/2)k + 1 + (k + 1/2 + 1/2) Rearrange (1/2)k 2 + k + 1/2 + (1/2)k + 1/2 + 1 Factor out 1/2 --> 1/2(k 2 + 2k + 1)

  2. matrix power

    Using technology, in this case our graphing calculators, we investigated what will happen with the more extreme values of k and n. We determined that the exact scope and limitations for k and n, is quite far ahead of the capabilities of the calculators.

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

    Diagram 11. Examples of Sae-Luk Gab-Oh is when a player gets two cards' numbers get added up and the 1st digit is 9. Diagram 12. Examples of Gab-Oh Gget is when a player gets two cards' numbers get added up and become 1 ~ 8 (8 is highest, 1 is lowest).

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

    well in English, but due to the weakness of the correlation, this assumption could be otherwise. The r� value shows that 56% of the variation in the modal mark earned by girls can be accounted by the number of books read.

  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. 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. The purpose of this investigation is to create and model a dice-based casino game ...

    Players may decide how much money to gamble, as in poker. Summary This investigation has analyzed various dice games, starting from the simple case where two players A and B roll one die each, with A winning if their rolled number is larger than that of player B.

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