# eudlidean algorithm,permutation.....

• Dec 29th 2006, 02:05 AM
m777
eudlidean algorithm,permutation.....
Hello,
please try to solve these questions.
m777
• Dec 29th 2006, 03:39 AM
topsquark
Use the Euclidean Algorithm to find gcd(190, 34).

Given two integers a and b (a > b) and the equation:
$\displaystyle a = q \cdot b + r$
where q and r are some integers (r < b).

The Euclidean Algorithm states that
$\displaystyle gcd(a, b) = gcd(b, r)$

By simple division we can find that:
$\displaystyle 190 = 5 \cdot 34 + 20$

Thus $\displaystyle gcd(190, 34) = gcd(34, 20)$.

Repeating this process on gcd(34, 20):
$\displaystyle 34 = 1 \cdot 20 + 14$

So $\displaystyle gcd(190, 34) = gcd(34, 20) = gcd(20, 14)$.

Continuing:
$\displaystyle 20 = 1 \cdot 14 + 6$
$\displaystyle gcd(190, 34) = gcd(34, 20) =$ $\displaystyle gcd(20, 14) = gcd(14, 6)$.

$\displaystyle 14 = 2 \cdot 6 + 2$
$\displaystyle gcd(190, 34) = gcd(34, 20) =$ $\displaystyle gcd(20, 14) = gcd(14, 6) = gcd(6, 2)$.

$\displaystyle 6 = 3 \cdot 2 + 0$

Now, this means that 2 is a divisor of 6, so we are done:
$\displaystyle gcd(190, 34) = gcd(34, 20) =$ $\displaystyle gcd(20, 14) = gcd(14, 6) = gcd(6, 2) = 2$.

Thus $\displaystyle gcd(190, 34) = 2$.

-Dan
• Dec 29th 2006, 03:52 AM
galactus
For #1b:

$\displaystyle P(n,r)=\frac{n!}{(n-r)!}$

$\displaystyle P(n,4)=\frac{n!}{(n-4)!}$

$\displaystyle 42P(n,2)=\cdot\frac{n!}{(n-2)!}$

$\displaystyle \frac{n!}{(n-4)!}=42\frac{n!}{(n-2)!}$

Using the definition of factorial, we can cancel terms in the denomiantors:

$\displaystyle \frac{n!}{(n-4)!}=\frac{n(n-1)(n-2)(n-3)(n-4)....}{(n-4)(n-5)(n-6)(n-7)....}$$\displaystyle =n(n-1)(n-2)(n-3)=n^{4}-6n^{3}+11n^{2}-6n$

Do the same for the other and we get $\displaystyle 42n(n-1)$

We have: $\displaystyle n^{4}-6n^{3}+11n^{2}-6n=42n^{2}-42n$

Which gives: $\displaystyle n^{4}-6n^{3}-31n^{2}+36n=0$

$\displaystyle n(n-9)(n-1)(n+4)$

Which gives : $\displaystyle n=0, \;\ 9, \;\ 1, \;\ -4$

• Dec 29th 2006, 05:45 AM
Soroban
Hello, m777!

Quote:

1(a) Use the Euclidean Algorithm to find $\displaystyle \text{gcd}(190,34)$

I was taught this way . . .

[1] Divide the larger by the smaller; note the remainder.
[2] Divide the remainder into the divisor; note the remainder.
[3] Repeat step 2 until the remainder is 0.
[4] The $\displaystyle \text{gcd}$ is the last divisor.
Code:

        5          1          1        2        3     ------      ----      ----      ----      ---   34 ) 190    20 ) 34    14 ) 20    6 ) 14    2 ) 6       170        20        14        12    ↑  6       ---        ---        ---      ---      --         20        14          6        2        0

Therefore: .$\displaystyle \text{gcd}(190,34) \:=\:2$

Quote:

1(b) Find $\displaystyle n$ if: $\displaystyle P(n,4) \:=\:42\!\cdot\!P(n,2)$

We have: .$\displaystyle \frac{n!}{(n-4)!} \:=\;42\!\cdot\!\frac{n!}{(n-2)!} \quad\Rightarrow\quad \frac{1}{(n-4)!} \:=$ $\displaystyle \:\frac{42}{(n-2)!}\quad\Rightarrow\quad (n-2)! \:=\:42(n-4)!$

Divide by $\displaystyle (n-4)!\!:\;\;(n-2)(n-3) \:=\:42\quad\Rightarrow\quad n^2 - 5n - 36 \:= \:0$

The quadratic factors: .$\displaystyle (n + 4)(n - 9) \:=\:0$
. . and has two solutions: .$\displaystyle n \:=\:-4,\:9$

Since $\displaystyle n$ must be positive, the answer is: .$\displaystyle \boxed{n \,= \,9}$

Quote:

2. A computer access code consists of from one to three letters
. . of the English alphabet with repetition allowed.
How many different code words are possible?

Since each code letter has 26 choices,
. . there are: .$\displaystyle 26 \times 26 \times 26 \:=\:17,576$ possible code words.

Quote:

3(a) A box contains 10 different colored light bulbs.
Find the number of ordered samples of size 3 with replacement.

The first can be any of the 10 bulbs.
The second can be any of the 10 bulbs.
The third can be any of the 10 bulbs.

There are: .$\displaystyle 10 \times 10 \times 10 \:=\:1,\!000$ possible ordered samples.

Quote:

3(b) How many possible outcomes are there when a fair coin is tossed three times?

The first toss has 2 possible outcomes (Heads or Tails).
The second toss has 2 possible outcomes.
The third toss has 2 possible outcomes.

There are: .$\displaystyle 2 \times 2 \times 2 \:=\:8$ possible outcomes.

Quote:

4. How many 2-permutations are there of $\displaystyle \{w,x,y,z\}$? .Write them all.

There are: .$\displaystyle P(4,2) \:=\:12$ permutations.

They are: .$\displaystyle \begin{Bmatrix}wx & wy & wz \\ xw & xy & xz \\ yw & yx & yz \\ zw & zx & zy\end{Bmatrix}$

• Dec 29th 2006, 07:08 AM
m777
excellent.........
Hello soroban,
you are genius.
from
m777