Solve 7 Digit Phone Number Combination Puzzle

[dipole]

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?

 

[coolul007]

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.

 

[mfb]

or how to construct a procedure to actually generate the list of possibilities?

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.

 

[Bacle2]

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'= a_n10ⁿ+a_k10^k- [ a_k10ⁿ+ a_n10^k]=

a_k(10ⁿ-10^k)+a_n(10^k -10ⁿ)

 

[dipole]

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.

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.

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'= a_n10ⁿ+a_k10^k- [ a_k10ⁿ+ a_n10^k]=

a_k(10ⁿ-10^k)+a_n(10^k -10ⁿ)

That's a neat fact, thanks.

 

[haruspex]

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.