MAT 305 Summer 1997

1. There are **[n - (k + 1)]*2!*(n -
2)!** different line ups.

Here's a drawing of the general situation:

If there are k people between Juanita (J) and Carlos (C), then if J is in the left most position, C will be in the (k + 1) position. We then slide J and C along, always with k people between them. When C is in the right-most position, position n, J is (k + 1) positions away, or in position [n - (k + 1)]. This helps show that there are [n - (k + 1)] different ways that J and C can have k people between them in a line with n people in all. For each of those positions, J and C can switch positions in 2! = 2 ways. Finally, the remaining n - 2 people can be arranged in (n - 2)! ways. We use the multiplication principle, multiplying the three values, because each is independent of the others.

Note the restrictions on the variables n and k: 0<=k<=(n-2).

2. There are 171 possible 4-digit codes.

To solve the problem, determine the number of possible rows where the first push could have occurred and then determine the number of possible pushes in each row. We must consider cases because not all rows have the same number of buttons available.

Label the rows A, B, C, and D, top to bottom, for ease of discussion. We cannot begin in row A (1,2,3) because there is no row above it. Thus, we have three rows as possible starting rows.

Case I: Begin in row B or C.

In these rows, there are 3 buttons to choose from for the first push. Moving up one row, to A or B, respectively, also yields 3 buttons to choose from for the second and third pushes. Finally, returning to the original row for the last push, there are 3 buttons to choose from. This gives us 2*3*3*3*3 = 2*3^4 = 162 dif ferent 4-digit codes.

Case II: Begin in row D.

Here there is just one choice for the first push, the button with digit 0. Moving up to row C, there are 3 buttons to choose from for the second and third pushes. Finally, returning to row D for the last push, there is 1 button to push. This gives us 1*1*3*3*1 = 3^2 = 9 different 4-digit codes.

(a) 1, 3, 9

S1 = 1! = 1,
S2 = 1! + 2! = 1 + 2 = 3,
S3 = 1! + 2! + 3! = 1 + 2 + 6 = 9.

(b) n = 1 and n = 3

We continue the pattern begun in (a):

S4 = 1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33,
and

S5 = 1! + 2! + 3! + 4! + 5! = 1 + 2 + 6 + 24 + 120 = 153.

S6 = 1! + 2! + 3! + 4! + 5! + 6! = 1 + 2 + 6 + 24 + 120 + 720 = 873.

Notice that for the sums S5 and beyond, we will always be adding terms that are multiples of 10. Thus, the sums S5 and beyond will always have a units digit of 3. But the units digits of perfect squares repeat the pattern 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, so no perfect square has 3 as its units digit. This means that the only perfect square sums are when n = 1 and n =3, as shown in (a).