1. ## Re: Discrete Maths Sem 2 2016

See I was kinda hoping for a cheat way out; a necessary AND sufficient condition :')

Not like those damn Hamilton circuits

2. ## Re: Discrete Maths Sem 2 2016

Okay figured it out:
- First we check if the graph exists by checking if all the degrees of each vertex sum to an even number.
- We then follow RealiseNothing's approach.
- We take note that if the vertex with highest degree is equal to or greater than the amount of vertices's if this is true a simple graph does not exist.
- You eliminate the vertex with the higher degree and subtract 1 from each of the vertex degrees until the number of times you subtract equal to the degree of the vertex you deleted. (I don't think this needs an explanation)
- You keep doing this and if at any point the max degree is greater than or equal to the amount verticies then there is no simple graph.
- If you reach 0 then a simple graph exists

Example:

4, 4, 3, 2, 2, 1

3, 2, 1, 1, 1

1, 1

0

Therefore a simple graph exists.

5, 5, 3, 2, 2, 1

4, 2, 1, 1

Therefore since the highest degree is equal to the total number of vertices's there is no simple graph.

3. ## Re: Discrete Maths Sem 2 2016

$x \sim y\text{ iff }\exists k \in \mathbb{Z}\text{ s.t. }x-y=2k\pi$

$\text{Proven in a): }\sim\text{ is an equivalence relation}\\ \text{Found in b): }\mathbb{R}\text{, partitioned into a set of equivalence classes }[x]\\ \text{for }x\in \mathbb{R}\text{ is}\\ \bigcup _{ x\in (-\pi ,\pi ] }\{ x+2k\pi \mid k \in \mathbb{Z} \}$

$\text{c) Find a bijection }\phi: (\mathbb{R} / \sim) \to \mathbb{T}\\\text{from the collection }(\mathbb{R}/\sim)\text{ of all equivalence classes }[x]\text{ of }\sim\\ \text{onto the unit circle }\mathbb{T}=\{z \in \mathbb{C}\mid |z|=1 \}\text{ in }\mathbb{C}\\ \text{Show carefully that }\phi\text{ is both injective and surjective.}$

So, admittedly it took me a bit too long to figure out that phi(x) = exp(ix). But now I'm a bit stumped.

Without assuming anything such as d/dx exp(ix) = i.exp(ix) (or rather preferably not, as discrete maths isn't expected to know this), how would you prove the injective and surjective part properly? Cause the answers just restated what we were trying to prove and that was just unconvincing

4. ## Re: Discrete Maths Sem 2 2016

Main idea is that exp(ix) will be onto because clearly any complex number on the unit circle can be written in the form e^{ix}, and it'll be one-to-one because two "essentially different" x's clearly yield two different points on the unit circle (as they'll have essentially different angles).

5. ## Re: Discrete Maths Sem 2 2016

$First we observe that \phi is well defined, because if x\sim y, then f(x)=\exp(ix)=\exp(i(y+2\pi k))=\exp(iy)\exp(2\pi k i) which established that \phi(x) is independent of our choice of representative for the equivalence class x.\\ \\ Next we observe that \phi is injective in almost the same way. If \phi(x)=\phi(y), we deduce \exp(i(\tilde{x}-\tilde{y}))=1 where \tilde{x},\tilde{y} are representatives of x,y respectively. Since \exp(z)=1 has solution z=2\pi k, we deduce \tilde{x}\sim \tilde{y} and hence x=y. Surjectivity follows from the fact that \exp(z) surjects from \mathbb{R} to the unit circle.\\ \\ Here we have used without proof the fact that the exponential function surjects from \mathbb{R} to \mathbb{T} and has zero set 2\pi \mathbb{Z}.$

$Depending on which definitions you work from, various amounts of work are required to prove these facts. I am sure that you would be allowed to assume them though, the very fact this problem takes place in the complex plane implies you need to know the basic properties of complex numbers. One of which is that there is a complex function exp that gives rise to polar coordinates, and satisfies the above properties.$

6. ## 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?

7. ## Re: Discrete Maths Sem 2 2016

Originally Posted by leehuan
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).)

8. ## Re: Discrete Maths Sem 2 2016

$\text{Assume that in the expansion of }(x+y+z)^{20}(x+y)^{15}\text{ all the like terms are collected.}\\ \text{How many distinct terms are there?}$

$\text{So I analysed the question by considering the general algebraic term }x^\alpha y^\beta z^\gamma\\ \text{Which must satisfy }\alpha+\beta+\gamma = 35$

$\text{However, subject to the condition }\gamma \le 15$

$\text{So I considered what I believed to be the complement:}\\ \text{The number of different terms there is, subject to the condition }\gamma \le 16$

$\text{So by the method of stars and bars I arrived at:}\\ \text{The number of distinct solutions for integers }\alpha,\beta,\gamma\text{ is given by:} \\\binom{37}{2} - \binom{21}{2}$

Is there a flaw in my working out?

9. ## Re: Discrete Maths Sem 2 2016

Originally Posted by leehuan
$\text{Assume that in the expansion of }(x+y+z)^{20}(x+y)^{15}\text{ all the like terms are collected.}\\ \text{How many distinct terms are there?}$

$\text{So I analysed the question by considering the general algebraic term }x^\alpha y^\beta z^\gamma\\ \text{Which must satisfy }\alpha+\beta+\gamma = 35$

$\text{However, subject to the condition }\gamma \le 15$

$\text{So I considered what I believed to be the complement:}\\ \text{The number of different terms there is, subject to the condition }\gamma \le 16$

$\text{So by the method of stars and bars I arrived at:}\\ \text{The number of distinct solutions for integers }\alpha,\beta,\gamma\text{ is given by:} \\\binom{37}{2} - \binom{21}{2}$

Is there a flaw in my working out?
Do you mean $\gamma \leq 20$ ?

10. ## Re: Discrete Maths Sem 2 2016

Originally Posted by leehuan
$\text{Assume that in the expansion of }(x+y+z)^{20}(x+y)^{15}\text{ all the like terms are collected.}\\ \text{How many distinct terms are there?}$

$\text{So I analysed the question by considering the general algebraic term }x^\alpha y^\beta z^\gamma\\ \text{Which must satisfy }\alpha+\beta+\gamma = 35$

$\text{However, subject to the condition }\gamma \le 15$

$\text{So I considered what I believed to be the complement:}\\ \text{The number of different terms there is, subject to the condition }\gamma \le 16$

$\text{So by the method of stars and bars I arrived at:}\\ \text{The number of distinct solutions for integers }\alpha,\beta,\gamma\text{ is given by:} \\\binom{37}{2} - \binom{21}{2}$

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.

11. ## Re: Discrete Maths Sem 2 2016

Whoops yeah meant that, thanks
_____________________________

$\text{Prove that }\gcd(a,b)=\gcd(a,a-b)$

12. ## Re: Discrete Maths Sem 2 2016

Originally Posted by leehuan
Whoops yeah meant that, thanks
_____________________________

$\text{Prove that }\gcd(a,b)=\gcd(a,a-b)$
Suppose gcd(a,a-b) = d_1.

d_1 = ax + (a-b)y

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

13. ## Re: Discrete Maths Sem 2 2016

Originally Posted by leehuan
Whoops yeah meant that, thanks
_____________________________

$\text{Prove that }\gcd(a,b)=\gcd(a,a-b)$
$\noindent (This is pretty much the foundation of the Euclidean Algorithm.) Let g = \gcd (a,b) and h = gcd(a, a-b), assuming (a,b) \neq (0,0). Note g divides both a and b, so it divides a-b too. Therefore, g \leq h, since h is the \emph{greatest} common divisor of a and a-b.$

$\noindent Similarly, h divides b, as b= a - (a-b), and h divides both a and a-b. Thus h \leq g. So h=g.$

14. ## Re: Discrete Maths Sem 2 2016

Originally Posted by Drsoccerball
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
Originally Posted by InteGrand
$\noindent (This is pretty much the foundation of the Euclidean Algorithm.) Let g = \gcd (a,b) and h = gcd(a, a-b), assuming (a,b) \neq (0,0). Note g divides both a and b, so it divides a-b too. Therefore, g \leq h, since h is the \emph{greatest} common divisor of a and a-b.$

$\noindent Similarly, h divides b, as b= a - (a-b), and h divides both a and a-b. Thus h \leq g. So h=g.$
Ah so just use divisibility properties! Excellent

15. ## 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

16. ## Re: Discrete Maths Sem 2 2016

yes

why not - just map out the values

17. ## 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.

18. ## Re: Discrete Maths Sem 2 2016

Originally Posted by Flop21
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

19. ## Re: Discrete Maths Sem 2 2016

Originally Posted by Flop21
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).

20. ## 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).

21. ## 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.

22. ## Re: Discrete Maths Sem 2 2016

Originally Posted by Flop21
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.)

23. ## Re: Discrete Maths Sem 2 2016

Originally Posted by InteGrand
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).

24. ## Re: Discrete Maths Sem 2 2016

Originally Posted by Flop21
But why do you do f(x) ≤ f(x), when it's f(x) ≤ g(x) i.e. g(x) != f(x).
$\noindent The definition of \preceq being a reflexive relation on S is f\preceq f for all f\in S (so \emph{same function both times}).$

25. ## 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.

Page 8 of 10 First ... 678910 Last

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•