Combinatorics question

  • Thread starter dipole
  • Start date
  • #1
538
148
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?
 

Answers and Replies

  • #2
coolul007
Gold Member
265
7
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.
 
  • #3
35,393
11,746
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.
 
  • #4
Bacle2
Science Advisor
1,089
10
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:
  • #5
538
148
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.
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,028
6,704
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.
 

Related Threads on Combinatorics question

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
400
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
706
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
14
Views
4K
  • Last Post
Replies
2
Views
783
  • Last Post
Replies
1
Views
1K
Top