MATH1081 Discrete Maths (2 Viewers)

[leehuan]

Re: Discrete Maths Sem 2 2016

How many strings of eight lowercase letters of the English alphabet contain:

c) the letters x and y, with x occurring before y (anywhere before y), if all the letters are distinct?


So I get the need to introduce ²⁴P₆. How would I finish it off from here?

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

How many strings of eight lowercase letters of the English alphabet contain:

c) the letters x and y, with x occurring before y (anywhere before y), if all the letters are distinct?


So I get the need to introduce ²⁴P₆. How would I finish it off from here?

Well if all the letters are distinct, the answer is by symmetry just (1/2)*N, where N is the no. of possible eight (distinct) letter strings of which two of the letters and x and y. I.e. N = (24C6)*(8!). (Can of course also write N as (8*7*(24P6).)

 

[leehuan]

Re: Discrete Maths Sem 2 2016











Is there a flaw in my working out?

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Is there a flaw in my working out?

Do you mean ?

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Is there a flaw in my working out?

When you change your gamma to less than 20 and then you have 37C2 - 16C2 which is the answer.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Whoops yeah meant that, thanks
_____________________________

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Whoops yeah meant that, thanks
_____________________________

Suppose gcd(a,a-b) = d_1.

d_1 = ax + (a-b)y

d_1 = a(x +y) + b(-y) = gcd(a,b)

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Whoops yeah meant that, thanks
_____________________________

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Suppose gcd(a,a-b) = d_1.

d_1 = ax + (a-b)y

d_1 = a(x +y) + b(-y) = gcd(a,b)

Thing with the Bezout lemma is that it's a one-way implication.

The reverse way doesn't imply "equals", it implies "divides" (check the notes)

So yeah I was thinking about the need to write the proof backwards to prove that they both divide each other, and hence blah

Ah so just use divisibility properties! Excellent

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Quick question cause I'm out of shape. Would you call f a bijection?

S={x in Z, 0 <= x <= 9}
f:S->S, f(x) = x^3 mod 10

 

[Shadowdude]

Re: Discrete Maths Sem 2 2016

yes


why not - just map out the values

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Hi hopefully I can just bump this thread with my questions.

Can someone help me do all the steps for solving 79x ≡ 5 (mod 98).


I find 1 | 5, hence there is 1 solution. Using euclid's algorithm, i get down to 1 = 17(79) - 23(98). Now what? I keep screwing these questions up and not sure why, I think I need someone to go through all the steps in detail, thanks.

 

[Shadowdude]

Re: Discrete Maths Sem 2 2016

Hi hopefully I can just bump this thread with my questions.

Can someone help me do all the steps for solving 79x ≡ 5 (mod 98).


I find 1 | 5, hence there is 1 solution. Using euclid's algorithm, i get down to 1 = 17(79) - 23(98). Now what? I keep screwing these questions up and not sure why, I think I need someone to go through all the steps in detail, thanks.

1 = 17*79 - 23*98

ok now take mod 98 both sides and then i think you'll figure out what to do next


or... multiply the equation by 5

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Hi hopefully I can just bump this thread with my questions.

Can someone help me do all the steps for solving 79x ≡ 5 (mod 98).


I find 1 | 5, hence there is 1 solution. Using euclid's algorithm, i get down to 1 = 17(79) - 23(98). Now what? I keep screwing these questions up and not sure why, I think I need someone to go through all the steps in detail, thanks.

Note that solving 79x ≡ 5 (mod 98) is equivalent to finding integers x and y such that 79x = 5 + 98y <==> 79x - 98y = 5. Since -y is an integer (as y is an integer), this is equivalent to writing 79x + 98b = 5 for some integer b.

So our goal is to express 5 in the form 79x + 98b for some integers x and b, and then we'll take x (the integer multiplying 79) as our answer.

By the way, 17(79) - 23(98) does not equal 1. (We can tell that it is in fact negative from a glance. It is less than 20*80 - 20*98 < 0.) So you might want to check your calculations.

We can use the Euclidean algorithm to express 1 (the gcd of 79 and 98) in the form 79A + 98B.

I.e. if you do the Euclidean algorithm correctly, you should end up writing

79A + 98B = 1, for some integers A and B.

Once you have this, you can multiply through by 5 to get 79*(5A) + 98*(5B) = 5, and so the "x" that we want as our solution would be 5A (modulo 98).

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

If you do the Euclidean algorithm calculations correctly, you should end up with something like -31*79 + 25*98 = 1.

Multiplying through by 5, we have the desired x as being (-31)*5 = -155 modulo 98, which is 41 modulo 98.

So the solution to the congruence is x ≡ 41 (mod 98).

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Thanks appreciate it guys!

________________

Can someone help me start this partial order proof, e.g. prove it's reflexive.

Let F be the set of all functions f: R -> R. A relation ⪯ is refined on F by

f ⪯ g if and only if f(x) ≤ g(x) for all x ϵ R.

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Thanks appreciate it guys!

________________

Can someone help me start this partial order proof, e.g. prove it's reflexive.

Let F be the set of all functions f: R -> R. A relation ⪯ is refined on F by

f ⪯ g if and only if f(x) ≤ g(x) for all x ϵ R.

Let S be the set of all functions from ℝ -> ℝ.

To show ⪯ is reflexive, we need to show that for every f in S, f ⪯ f. This is quite straightforward:

Let f be any element of S. Then clearly for every x in ℝ, we have f(x) ≤ f(x) (this is implied by the trivial fact that f(x) = f(x) for all x).

Thus by definition, f ⪯ f. This is the case for every f in S, so ⪯ is a reflexive relation on S.

(I just realised now that the set was already given the name F. So you can replace all my S's with F's if you want.)

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Let S be the set of all functions from ℝ -> ℝ.

To show ⪯ is reflexive, we need to show that for every f in S, f ⪯ f. This is quite straightforward:

Let f be any element of S. Then clearly for every x in ℝ, we have f(x) ≤ f(x) (this is implied by the trivial fact that f(x) = f(x) for all x).

Thus by definition, f ⪯ f. This is the case for every f in S, so ⪯ is a reflexive relation on S.

(I just realised now that the set was already given the name F. So you can replace all my S's with F's if you want.)

But why do you do f(x) ≤ f(x), when it's f(x) ≤ g(x) i.e. g(x) != f(x).

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

But why do you do f(x) ≤ f(x), when it's f(x) ≤ g(x) i.e. g(x) != f(x).

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Hello, I'm on a mission to understand proofs. It's going to be tricky for me but hopefully some people can help me out here.


My first question is about a proof (by contradiction) regarding log6(11) being irrational.

So the proof assumes p, q > 0 ... then fast forward and finds 11^q = 6^p, then says "which is a contradiction, as the LHS is always odd and RHS is always even".

Why is the LHS and RHS being odd/even make it a contradiction? Thanks.