Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics question

  1. Aug 23, 2012 #1
    Suppose you have written down a seven digit phone number, but you realize you made a mistake and two of the digits are interchanged. For example, suppose the correct number is 345-6789, but you have on accident written down 348-6759.

    Sticking to the general case though, where you have seven digits in a specific order, and only two of them are out of place - how many possible combinations must you try in order to find the correct number?

    The brute force way would be to just try every permutation, 7! but that includes a huge number of combinations which are impossible to be correct - the correct combination must only switch two digits from the original set.

    Any ideas how to solve this, or how to construct a procedure to actually generate the list of possibilities?
     
  2. jcsd
  3. Aug 23, 2012 #2
    if you know it is only 2 numbers that are switched, then you have 7 things taken 2 at a time or 7!/(2!)(5!) or 21, 2 number combinations to switch.
     
  4. Aug 23, 2012 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Exchange digit 1 with 2, 1 with 3, ..., 1 with 7, 2 with 3, 2 with 4, ..., 2 with 7, ..., ..., 6 with 7.

    For phone numbers where digits appear multiple times, some of those switches give the original number and reduce the number of possible phone numbers.
     
  5. Aug 23, 2012 #4

    Bacle2

    User Avatar
    Science Advisor

    One trick that may be helpful:

    When a number x in decimal notation has exactly two digits swapped,with the swapped

    number being x', then 9 divides the difference x-x'. In your case:

    3486759-3456789=29970.

    Basically, x-x'= an10n+ak10k- [ ak10n+ an10k]=

    ak(10n-10k)+an(10k -10n)
     
    Last edited: Aug 23, 2012
  6. Aug 23, 2012 #5
    Ah duh, this makes the problem easy. There are six possible pairs for each starting digit, and seven different digits giving 42 different swaps, but each swap is doubly degenerate, reducing the number by halve to give what coolul007 posted, which is 21.

    For some reason I am just terrible at combinatorial stuff, but this is actually an easy question.

    That's a neat fact, thanks.
     
  7. Aug 23, 2012 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, 21 if the digits are all different, but fewer if there are repeated digits. So in general it breaks down into lots of cases: all different, 1 pair the same, 2 pairs the same, 3 the same, ... The number of cases is a partition number.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics question
  1. Combinatorics question (Replies: 1)

  2. Combinatorics question (Replies: 3)

Loading...