Page 8 of 10 FirstFirst ... 678910 LastLast
Results 176 to 200 of 236
Like Tree87Likes

Thread: MATH1081 Discrete Maths

  1. #176
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    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. #177
    Loquacious One Drsoccerball's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Undisclosed
    Posts
    3,668
    Rep Power
    5

    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.
    leehuan likes this.

  3. #178
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    Re: Discrete Maths Sem 2 2016








    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. #179
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    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).
    leehuan likes this.

  5. #180
    Supreme Member seanieg89's Avatar
    Join Date
    Aug 2006
    HSC
    2007
    Gender
    Male
    Posts
    2,620
    Rep Power
    9

    Re: Discrete Maths Sem 2 2016



    Last edited by seanieg89; 11 Nov 2016 at 2:23 PM.
    leehuan likes this.

  6. #181
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    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. #182
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by leehuan View Post
    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 by InteGrand; 11 Nov 2016 at 4:06 PM.
    leehuan likes this.

  8. #183
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    Re: Discrete Maths Sem 2 2016











    Is there a flaw in my working out?

  9. #184
    Loquacious One Drsoccerball's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Undisclosed
    Posts
    3,668
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by leehuan View Post










    Is there a flaw in my working out?
    Do you mean ?
    leehuan likes this.

  10. #185
    Loquacious One Drsoccerball's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Undisclosed
    Posts
    3,668
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by leehuan View Post










    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 likes this.

  11. #186
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    Re: Discrete Maths Sem 2 2016

    Whoops yeah meant that, thanks
    _____________________________


  12. #187
    Loquacious One Drsoccerball's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Undisclosed
    Posts
    3,668
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by leehuan View Post
    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)
    leehuan likes this.

  13. #188
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by leehuan View Post
    Whoops yeah meant that, thanks
    _____________________________



    Last edited by InteGrand; 13 Nov 2016 at 12:28 AM.
    leehuan likes this.

  14. #189
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by Drsoccerball View Post
    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
    Quote Originally Posted by InteGrand View Post


    Ah so just use divisibility properties! Excellent

  15. #190
    Ancient Orator leehuan's Avatar
    Join Date
    May 2014
    HSC
    2015
    Gender
    Male
    Posts
    5,774
    Rep Power
    6

    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. #191
    Cult of Personality Shadowdude's Avatar
    Join Date
    Sep 2009
    HSC
    2010
    Gender
    Male
    Posts
    12,215
    Rep Power
    14

    Re: Discrete Maths Sem 2 2016

    yes


    why not - just map out the values
    leehuan likes this.
    B Arts / B Science (Advanced Mathematics), UNSW

  17. #192
    Supreme Member Flop21's Avatar
    Join Date
    May 2013
    HSC
    2015
    Gender
    Female
    Posts
    2,847
    Rep Power
    5

    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.
    turntaker likes this.
    2015 HSC: English Adv, Mathematics, Business Studies, Biology, Multimedia.

    HSC Biology Flashcards

  18. #193
    Cult of Personality Shadowdude's Avatar
    Join Date
    Sep 2009
    HSC
    2010
    Gender
    Male
    Posts
    12,215
    Rep Power
    14

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by Flop21 View Post
    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
    Flop21 likes this.
    B Arts / B Science (Advanced Mathematics), UNSW

  19. #194
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by Flop21 View Post
    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 by InteGrand; 2 Apr 2017 at 3:30 PM.
    Flop21 and kawaiipotato like this.

  20. #195
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    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 likes this.

  21. #196
    Supreme Member Flop21's Avatar
    Join Date
    May 2013
    HSC
    2015
    Gender
    Female
    Posts
    2,847
    Rep Power
    5

    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.
    2015 HSC: English Adv, Mathematics, Business Studies, Biology, Multimedia.

    HSC Biology Flashcards

  22. #197
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by Flop21 View Post
    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 likes this.

  23. #198
    Supreme Member Flop21's Avatar
    Join Date
    May 2013
    HSC
    2015
    Gender
    Female
    Posts
    2,847
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by InteGrand View Post
    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).
    2015 HSC: English Adv, Mathematics, Business Studies, Biology, Multimedia.

    HSC Biology Flashcards

  24. #199
    Ancient Orator
    Join Date
    Dec 2014
    HSC
    N/A
    Gender
    Male
    Posts
    5,929
    Rep Power
    5

    Re: Discrete Maths Sem 2 2016

    Quote Originally Posted by Flop21 View Post
    But why do you do f(x) ≤ f(x), when it's f(x) ≤ g(x) i.e. g(x) != f(x).
    Flop21 likes this.

  25. #200
    Supreme Member Flop21's Avatar
    Join Date
    May 2013
    HSC
    2015
    Gender
    Female
    Posts
    2,847
    Rep Power
    5

    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.
    2015 HSC: English Adv, Mathematics, Business Studies, Biology, Multimedia.

    HSC Biology Flashcards

Page 8 of 10 FirstFirst ... 678910 LastLast

Thread Information

Users Browsing this Thread

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
  •