CourseworkHelp

Baker’s Dozen

'font-size:14.0pt; '>1. The baker’s wife needs to rearrange the row of Bath Buns (B) and Chelsea Buns (C) from C B C B C B to C C C B B B by swapping a bun with its neighbour in the smallest possible number of moves.

Let us from now on give each bun its own identification, so it is easy to differentiate between like buns (e.g. C1'font-size:14.0pt; '>, C2, C3,). Thus the row starts off looking like this:

C1 B1 C2 B2 C3 B3

The baker’s wife is putting all Bath Buns to the right. She starts by swapping C3 (i.e. the furthest right C) with the B to its left (i.e. B2):

Therefore C1 B1 C2 B2 C3 B3 becomes

C1 B1 C2 C3 B2 B3 in a single swap

This leaves B1 isolated in the left half of the row (where C2 should be). Therefore B1 has to be moved in the smallest number of swaps. First, B1 is swapped with C2:

So C1 B1 C2 C3 B2 B3 becomes

C1 C2 B1 C3 B2 B3 after a single swap

And then B1 is swapped with C3 to finally become:

C1 C2 C3 B1 B2 B3 (after 3 swaps)

After further investigation with counters, I concluded that the smallest number of swaps the baker’s wife needs to make to sort out the row of 3Cs and 3Bs is THREE.

'font-size:14.0pt; '>2. In this question I am intending to find a formula to calculate the number of swaps for any number of buns.

'font-size:14.0pt; '>First, using exactly the same method as that used in Question1, I will find out what the smallest number of swaps needed to sort out a row of 2Cs and 2Bs is.

ThereforeI start off with 2Cs and 2Bs as so

And C1 B1 C2 B2 becomes

C1 C2 B1 B2 after a single swap

Therefore the number of swaps needed to sort out a row of 2Cs and 2Bs is ONE

As found in the previous question, the smallest number of swaps needed to sort out the row of 3Cs and 3Bs is THREE.

Now I will find out the smallest number of swaps need to sort out a row of 4Bs and 4Cs, again using the same method and starting off in the same way (i.e. C1 B1 C2 B2 C3 B3 C4 B4)

From here I move all Bs to the right and all Cs to the left. Therefore B3 swaps with B4 as so:

C1 B1 C2 B2 C3 B3 C4 B4 becomes

C1 B1 C2 B2 C3 C4 B3 B4 after a single swap, which then becomes

C1 C2 B1 B2 C3 C4 B3 B4 after another.

This leaves C3 and C4 isolated in-between all 4 Bs, so:

C1 C2 B1 B2 C3 C4 B3 B4 becomes

C1 C2 B1 C3 B2 C4 B3 B4 after another swap, and so the movements carry on thus, so that

C1 C2 B1 C3 B2 C4 B3 B4 (previous sequence) becomes

C1 C2 B1 C3 C4 B2 B3 B4, which becomes

C1 C2 C3 B1 C4 B2 B3 B4, and then finally B1 and C4 swap to become

C1 C2 C3 C4 B1 B2 B3 B4 and we have finally reached our objective!

'font-size:14.0pt; '>Therefore, one can conclude that the smallest number of swaps needed to sort out the row of 4Cs and 4Bs is SIX.

I have now reached a point where I think that I can see a pattern. All the numbers of swaps so far have been Triangular numbers. This would suggest that if the number of swaps was represented by the letter S and the letter n the number of each colour of counter, S=1+2+3…+ (n-1)

So (SEE SHEET, eq. 1)

S=1+2+3…+ (n-1) (or S= (n-1)+(n-2)+(n-3)…+1, whichever way you want to look at it.)

Now this is where the clever part comes in!

If you add together the two different expressions above, 2S=n+n+n…+n

Therefore 2S= n (n-1)

Therefore S= n (n-1)

For this question, it is essential for me to investigate the number of swaps for various situations (variables).

'font-size:14.0pt; '>Variable 1

Firstly, I will investigate the number of swaps if another type of bun, Hot Cross Buns, is added to the row. The buns will be arranged in the following order in the shop window:

C B H C B H C B H…

The aim of the investigation will be how to see many swaps will have to be made to sort the buns into a row similar to that in Q. 1:

C C C … B B B … H H H …

Obviously, when there is only one ‘iteration’ (i.e. simply C B H), the number of swaps needed to be made is ZERO, because the row is already in order.

Now I will find out how the number of swaps needed to be made when there are 2 iterations, (tabulated as before). From here, the most sensible move is to swap C2 with H1, so

C1 B1 H1 C2 B2 H2 becomes

C1 B1 C2 H1 B2 H2 after a single swap, and so on as so:

C1 C2 B1 H1 B2 H2

C1 C2 B1 B2 H1 H2.

Therefore, one can conclude that the smallest number of swaps needed to sort out the row of 2Cs and 2Bs and 2 Hs is THREE.

Now I will find out how many moves are needed when there are three iterations to sort out the row.

We start as

C1 B1 H1 C2 B2 H2 C3 B3 H3, which becomes

C1 B1 C2 H1 B2 H2 C3 B3 H3 after a single move, and so on as so:

C1 B1 C2 H1 B2 C3 H2 B3 H3

C1 C2 B1 H1 B2 C3 H2 B3 H3

C1 C2 B1 H1 B2 C3 B3 H2 H3

C1 C2 B1 H1 C3 B2 B3 H2 H3

C1 C2 B1 C3 H1 B2 B3 H2 H3

C1 C2 C3 B1 H1 B2 B3 H2 H3

C1 C2 C3 B1 B2 H1 B3 H2 H3

C1 C2 C3 B1 B2 B3 H1 H2 H3- 9 moves!

Therefore, one can conclude that the smallest number of swaps needed to sort out the row of 3Cs and 3Bs and 3Hs is NINE.

Now I will find out how many moves are needed when there are four iterations to sort out the row.

We start as

C1 B1 H1 C2 B2 H2 C3 B3 H3 C4 B4 H4, which becomes

C1 B1 C2 H1 B2 H2 C3 B3 H3 C4 B4 H4 after a single move, and so on as so:

C1 C2 B1 H1 B2 H2 C3 B3 H3 C4 B4 H4

C1 C2 B1 H1 B2 H2 C3 B3 C4 H3 B4 H4

C1 C2 B1 H1 B2 H2 C3 B3 C4 B4 H3 H4

C1 C2 B1 H1 B2 C3 H2 B3 C4 B4 H3 H4

C1 C2 B1 H1 C3 B2 H2 B3 C4 B4 H3 H4

C1 C2 B1 C3 H1 B2 H2 B3 C4 B4 H3 H4

C1 C2 C3 B1 H1 B2 H2 B3 C4 B4 H3 H4

C1 C2 C3 B1 H1 B2 H2 C4 B3 B4 H3 H4

C1 C2 C3 B1 H1 B2 C4 H2 B3 B4 H3 H4

C1 C2 C3 B1 H1 C4 B2 H2 B3 B4 H3 H4

C1 C2 C3 B1 C4 H1 B2 H2 B3 B4 H3 H4

C1 C2 C3 C4 B1 H1 B2 H2 B3 B4 H3 H4

C1 C2 C3 C4 B1 B2 H1 H2 B3 B4 H3 H4

C1 C2 C3 C4 B1 B2 H1 B3 H2 B4 H3 H4

C1 C2 C3 C4 B1 B2 B3 H1 H2 B4 H3 H4

C1 C2 C3 C4 B1 B2 B3 H1 B4 H2 H3 H4, and finally

C1 C2 C3 C4 B1 B2 B3 B4 H1 H2 H3 H4 – 18 moves!

It is now possible to see a pattern developing:

1 iteration (i.e. 1 of each kind of bun)= 0 moves

2 iterations (i.e. 2 of each kind of bun)=3 moves

3 iterations (i.e. 3 of each kind of bun)=9 moves

4 iterations (i.e. 4 of each kind of bun)=18 moves

From here we can work out a formula to calculate the number of swaps needed for any number of iterations when there are three kinds of bun, using the ‘automatic’ method:

(SEE SEPARATE EQUATIONS SHEET, eq. 2)

Variable 2

Secondly, I will investigate the number of swaps if the buns are arranged, not so that they are in a row next to each other, C B C B C BC B, but so that there are two of one type next to each other, i.e. CC BB CC BB.

I will start with one ‘iteration’ (i.e. simply CC BB). There are obviously ZERO moves needed to be made, because all the Cs are already to the left and the Bs to the right- the job is done for us!

Now I will find how many moves are to be made when there are two iterations.

We start as C1 C2 B1 B2 C3 C4 B3 B4, which becomes

C1 C2 B1 C3 B2 C4 B3 B4 after a single swap. We carry on as so:

C1 C2 C3 B1 B2 C4 B3 B4

C1 C2 C3 B1 C4 B2 B3 B4

C1 C2 C3 C4 B1 B2 B3 B4- 4 moves!

Now I will find out how many moves need to be made when there are three iterations.

C1 C2 B1 B2 C3 C4 B3 B4 C5 C6 B5 B6 becomes

C1 C2 B1 C3 B2 C4 B3 B4 C5 C6 B5 B6

after a single swap, and so on:

C1 C2 C3 B1 B2 C4 B3 B4 C5 C6 B5 B6

C1 C2 C3 B1 C4 B2 B3 B4 C5 C6 B5 B6

C1 C2 C3 C4 B1 B2 B3 B4 C5 C6 B5 B6

C1 C2 C3 C4 B1 B2 B3 C5 B4 C6 B5 B6

C1 C2 C3 C4 B1 B2 C5 B3 B4 C6 B5 B6

C1 C2 C3 C4 B1 C5 B2 B3 B4 C6 B5 B6

C1 C2 C3 C4 C5 B1 B2 B3 B4 C6 B5 B6

C1 C2 C3 C4 C5 B1 B2 B3 C6 B4 B5 B6

C1 C2 C3 C4 C5 B1 B2 C6 B3 B4 B5 B6

C1 C2 C3 C4 C5 B1 C6 B2 B3 B4 B5 B6

C1 C2 C3 C4 C5 C6 B1 B2 B3 B4 B5 B6- 12 moves.

1 ‘iteration’ (or 4 buns, 2 of each type) = 0 moves

2 iterations (or 8 buns, 4 of each type) = 4 moves

3 iterations (or 12 buns, 6 of each type) =12 moves

From here we can make an equation.

(SEE SEPARATE EQUATION SHEET. Eq. 3)

(? From this we can predict that the number of moves needed to be taken when there are 4 iterations (n= 4) is 24. ?)

If you still can't find any of the coursework that you are looking for, click here to look at over 30,000 GCSE, A-Level and University Level essays on Coursework.Info.