Forum — Daily Challenge
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups
    • Login

    Complementary counting solution for mini-question

    Module 3 Day 12 Your Turn Part 3
    2
    2
    21
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • P
      professionalbronco M0★ M1★ M2★ M3 M5★
      last edited by

      The total number of ways to color a graph like this Graph.JPG
      is the same as the number of ways to color a graph like this
      Graph1.JPG
      minus the number of ways to color a graph like this
      Graph2.JPG.
      The number of ways to color a graph shown in graph #2 is just

      $$(3\times 2\times 2\times 2)\times (3\times 2\times 2)=288. $$

      Remember that there would be a 1/3 probability for these two nodes to have the same color.Graph4.JPG
      So there are a total of \(\dfrac{1}{3}\times 288=96\) "bad" ways.
      Thus, we get an answer of

      $$(\text{\# of ways to color the original graph})=288-96=\boxed{192}. $$

      In other words, this is the same as \(\left(1-\dfrac{1}{3}\right)\times 288=\boxed{192}.\)

      The Daily Challenge with Po-Shen Loh is the best!
      aops user = captainnobody

      quacker88Q 1 Reply Last reply Reply Quote 3
      • quacker88Q
        quacker88 MOD @professionalbronco
        last edited by

        @professionalbronco Really smart use of complementary counting! It's always super cool when a totally different solution is found. Great job!

        1 Reply Last reply Reply Quote 2

        • 1 / 1
        • First post
          Last post
        Daily Challenge | Terms | COPPA