Page 8 of 8 FirstFirst ... 678
Results 176 to 191 of 191
Like Tree67Likes

Thread: Discrete Maths Sem 2 2016

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

    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,656
    Rep Power
    4

    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,555
    Rep Power
    5

    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,422
    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,562
    Rep Power
    9

    Re: Discrete Maths Sem 2 2016



    Last edited by seanieg89; 11 Nov 2016 at 2:23 PM.
    leehuan likes this.
    Currently studying:
    PhD (Pure Mathematics) at ANU

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

    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,422
    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,555
    Rep Power
    5

    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,656
    Rep Power
    4

    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,656
    Rep Power
    4

    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,555
    Rep Power
    5

    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,656
    Rep Power
    4

    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,422
    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,555
    Rep Power
    5

    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,555
    Rep Power
    5

    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,149
    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

Page 8 of 8 FirstFirst ... 678

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
  •