MATH1081 Discrete Maths (1 Viewer)

leehuan

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
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 24P6. How would I finish it off from here?
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
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 24P6. 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).)
 
Last edited:

leehuan

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
Re: Discrete Maths Sem 2 2016











Is there a flaw in my working out?
 

leehuan

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
Re: Discrete Maths Sem 2 2016

Whoops yeah meant that, thanks
_____________________________

 

leehuan

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
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

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
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
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
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

Cult of Personality
Joined
Sep 19, 2009
Messages
12,146
Gender
Male
HSC
2010
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

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
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).
 
Last edited:

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
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

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
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

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
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

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
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).
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
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.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top