# Combinatorics question

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
Gold Member
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
Mentor
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'= an10n+ak10k- [ ak10n+ an10k]=

ak(10n-10k)+an(10k -10n)

Last edited:
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'= an10n+ak10k- [ ak10n+ an10k]=

ak(10n-10k)+an(10k -10n)

That's a neat fact, thanks.

haruspex