We want to choose telephone numbers for a city. The numbers have $10$ digits and $0$ isn’t used in the numbers. Our aim is: We don’t choose some numbers such that every $2$ telephone numbers are different in more than one digit OR every $2$ telephone numbers are different in a digit which is more than $1$. What is the maximum number of telephone numbers which can be chosen? In how many ways, can we choose the numbers in this maximum situation?
Problem
Source:
Tags: combinatorics unsolved, combinatorics
siavosh
12.04.2012 21:00
no one can solve it ?
meysam1371
11.07.2016 14:34
any solution? this looks hard...
AlirezaOpmc
01.04.2018 19:11
Answer is $\frac{9^n+1}{2}$ by inducyion on. But can any one solve this problem by complex numbers? Same as the first example of 'problems from the book' at combinatrocal complex...
AgentC
10.01.2024 14:26
actually the key point is to work with n digits instead of 10 digits, this way we can start with small n and find the pattern. After that we use induction to prove at most \(\frac{9^{n}+1}{2}\) numbers can be chosen and the only way is to choose numbers which the sum of it's digits has the same parity as n. putting all of the possible numbers in a \(9\cdot (9^{n-1})\) matrix might as well help to have a better understanding.