187 – Quiz 8

Here is quiz 8.

Problem 1 asks to find integers x,y such that 13 x+8y=1. 

One way of doing this is to follow the Euclidean algorithm to compute the g.c.d. of 13 and 8:

{\mathbf 13}={\mathbf 8}\times1+{\mathbf 5},

{\mathbf 8}={\mathbf 5}\times1+{\mathbf 3},

{\mathbf 5}={\mathbf 3}\times1+{\mathbf 2},

{\mathbf 3}={\mathbf 2}\times1+{\mathbf 1}.

Now we work from these equations, starting with the last one and going up, expressing the remainders as linear combinations of the other two numbers:

1=3-2.

Since 2=5-3, we have 1=3-(5-3)=3\times2-5.

Since 3=8-5, we have 1=(8-5)\times2-5=8\times 2-5\times3.

Since 5=13-8, we have 1=8\times 2-(13-8)\times3=8\times 5-13\times3.

We have found that x=-3, y=5 satisfy 13x+8y=1. 

There are, of course, other ways we could have found these numbers, including trial and error: Simply list the multiples of 13 in order: 13, 26, 39, …, and note that 39 is 1 shy of a multiple of 8: 13\times 3=8\times 5-1, giving the same solution as before.

Problem 2 asks for integers x,y, neither of which is 0, and such that 13x+8y=0.

Perhaps the easiest solution is to make x=8, y=-13.

Problem 3 asks for integers x,y different from those in problem 1, such that 13x+8y=1.

One way of finding these numbers is by adding the solutions to problems 1 and 2:

13\times(-3)+8\times 5=1,

13\times8+8\times(-13)=0,

so

13\times 5+8\times(-8)=1.

We could have also subtracted the solution to problem 2 from the solution to problem 1, to obtain 13\times(-11)+8\times18=1.

Or we could have squared the solution to problem 1: (13\times(-3)+8\times 5)^2=1^2=1, or

13^2\times 9+2\times13\times(-3)\times8\times5+8^2\times25=1, or

13\times(13\times9+2\times-3\times8\times5)+8\times(8\times25)=1.

Problem 4 asks  for the number of injective functions from A=\{a,b,c,d\} into B=\{1,2,3,4,5\}.

Let f:A\to B be 1-1. There are 5 possibilities for the value f(a). Whatever it is, f(b) can take any value in B other than f(a), so there are 4 possibilities for f(b). The value f(c) can be anything in B other than f(a) or f(b), so there are 3 possibilities for f(c). Finally, f(d) can take any of the remaining 2 values. This gives a total of 5\times4\times 3\times 2=120 injective functions.

Note that this is the same as the number of lists of length 4 without repetitions with values taken from the set B.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: