1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a combinatorics puzzle - not able to get all combinations

  1. Apr 23, 2012 #1
    Hi,

    My question is related to a math puzzle. The puzzle asks to swap any two digits from the numerator with any two digits in the denominator of the fraction 1630 / 4542 to get the ratio 1 / 3.

    Two possible answers are 1534 / 4602 and 1354/ 4062.

    What I am struggling with is the number of possible combinations we would have if we were to use brute force to solve this problem. The solution of the problem says that there are 8! (i.e. 40,320) possible combinations. My analysis gets me only 144 combinations.

    Here is my analysis :There are 12 ways to pick a pair from the numerator and there are 12 ways to pick a pair from the denominator. A pair from the numerator can replace any one of the 12 pairs in the denominator. As a result there are 12x12 =144 combinations.

    What am I missing?

    Thank you.
     
  2. jcsd
  3. Apr 23, 2012 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Start with an easier situation, where all 8 digits are different. You are right that you can pick two digits from the numerator 12 ways and two digits from the denominator 12 ways. You missed the fact that you can write the four digits that form the new numerator in any order, and similarly for the denominator. Look at the second example where 1630 becomes 1354. The digit 3 has moved position.

    Warning: be careful about double-counting, because if you count say "10" and "01" as different ways to select two digits from the numerator, they will lead to the SAME set of denominators when you shuffle the four digits into any order.

    You are also missing the fact that there are two 4's in the denominator, which means (1) there are fewer ways to select two digits from the denominator, and (2) the number of ways you can order the digits after swapping them depends on whether you selected zero, one, or two of the 4s.
     
    Last edited: Apr 23, 2012
  4. Apr 24, 2012 #3
    Thanks AlephZero.

    It is still not clear to me. Also in my analysis I did not assume that I can shift / rotate numbers in either in the numerator or denominator. I want to keep it that way. Here is my another stab at the problem.

    Here I use letters instead of numbers to make it a bit simpler. In the numerator, we have ABCD and EFGH in the denominator. I assumed that we pull out any two letters from the numerator (6 ways of doing that ). I also do the same thing for the denominator (6 ways).
    A _ C _

    E _ _ H

    Now I take the 2 letters from the numerator and throw them in the 2 slots in the denominator (2 ways). In the same way I place the two letters from the denominator in the numerator (2 ways)

    In total, there are 6 x 6 x 2 x 2 = 144 ways

    Is that correct?
     
  5. Apr 24, 2012 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    I think that's correct, but it is not the same situation as the examples you originally posted. You can't change 1630 into 1534 by pulling out the 60 and replacing them. You have to move the 3 as well.

    But to be honest I don't see a simple reason why the answer should be 8!. With no repeated numbers, my interpretation of the question gives 6 x 6 x 24 x 24 = 20736, compared with 8! = 40320. With the repeated 4's there will be fewer than 20736 but too lazy to work out exactly how many.

    There are obviosuly 8! possible ways to shuffle 8 different digits, if there are no restrictions on how many you choose from the numerator of the denominator. Maybe that is what the book meant :confused:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving a combinatorics puzzle - not able to get all combinations
Loading...