Find the largest possible number n of three-digit numbers, following a set of properties

139 Views Asked by At

I just recently solved the following problem

Let n three-digit numbers satisfy the following properties:

(1) No number contains the digit 0.

(2) The sum of the digits of each number is 9

(3) The units digits of any two numbers are different.

(4) The tens digits of any two numbers are different.

(5) The hundreds digits of any two numbers are different.

Find the largest possible value of n.

I solved it in the following way:

I state that ai, bi, ci are the hundreds, tens and ones digits of the ith number respectively.

Since $ai, bi, ci\neq 0$ we have that $7\ge ai, bi, ci\ge 1$ for all $ai, bi, ci\in N$ and $ai, bi, ci \in [1, 7]$ (since from (2) we have that the addition of $ai+bi+ci=9$)

If $n=7$

Then $\sum\limits_{i=1}^7ai+bi+ci=63$, however $\sum\limits_{i=1}^7ai+bi+ci=3(1+...+7)=84$ (which is the addition of the digits, from property (2)), which is false.

Since $ai, bi, ci\in[1, 7]$, then if n=6 $\sum\limits_{i=1}^6 3(ai+bi+ci)\ge84-3*7=63$, however, once again $\sum\limits_{i=1}^6 ai+bi+ci=54$, so impossible. So maxn=5 for the set of {135, 243, 351, 414, 522}.

Once I wrote this out, I was wondering if there exists a simpler method of solving it. Could you please show me some alternative methods?

2

There are 2 best solutions below

0
On BEST ANSWER

As you notice $ n \leq 7$. Now, let's assume we can take full advantage of n, meaning that all numbers from $1$ to $n$ appear in every position. Summing the numbers gives $9n$ as you said but also $3$ times the sum of natural numbers up to $n$. Therefore,

$ 3 \frac{n(n+1)}{2} = 9n \implies n = 5$

The set you gave as answer satisfies this property. Finally, since both $n = 6$ and $n = 7$ cannot be fully used, they can give a set of size at most $n - 1$. So we only have to check if we can have a set of size 6 with it's largest number being 7. 7 can only appear in $7 + 1 + 1$ using both 1's so 6 cannot appear. 5 can now only appear as $5 + 2 + 2$ using both 2's so 4 cannot appear. And we are done!

0
On

You can get a short certificate of optimality via linear programming duality. Let $$S=\{117,126,135,144,153,162,171,216,225,234,243,252,261,315,324,333,342,351,414,423,432, 441,513,522,531,612,621,711\}$$ be the set of numbers that satisfy properties 1 and 2. For $j \in S$, let binary decision variable $x_j$ indicate whether $j$ is selected. The problem is to maximize $\sum_{j\in S} x_j$ subject to linear constraints, with optimal dual multipliers in parentheses: \begin{align} x_{171} + x_{261} + x_{351} + x_{441} + x_{531} + x_{621} + x_{711} &\le 1 &&(4/8)\\ x_{162} + x_{252} + x_{342} + x_{432} + x_{522} + x_{612} &\le 1 &&(3/8)\\ x_{153} + x_{243} + x_{333} + x_{423} + x_{513} &\le 1 &&(2/8)\\ x_{144} + x_{234} + x_{324} + x_{414} &\le 1 &&(1/8)\\ x_{135} + x_{225} + x_{315} &\le 1 &&(0)\\ x_{126} + x_{216} &\le 1 &&(0)\\ x_{117} + x_{216} + x_{315} + x_{414} + x_{513} + x_{612} + x_{711} &\le 1 &&(5/8)\\ x_{126} + x_{225} + x_{324} + x_{423} + x_{522} + x_{621} &\le 1 &&(4/8)\\ x_{135} + x_{234} + x_{333} + x_{432} + x_{531} &\le 1 &&(3/8)\\ x_{144} + x_{243} + x_{342} + x_{441} &\le 1 &&(2/8)\\ x_{153} + x_{252} + x_{351} &\le 1 &&(1/8)\\ x_{162} + x_{261} &\le 1 &&(0)\\ x_{117} + x_{126} + x_{135} + x_{144} + x_{153} + x_{162} + x_{171} &\le 1 &&(5/8)\\ x_{216} + x_{225} + x_{234} + x_{243} + x_{252} + x_{261} &\le 1 &&(4/8)\\ x_{315} + x_{324} + x_{333} + x_{342} + x_{351} &\le 1 &&(3/8)\\ x_{414} + x_{423} + x_{432} + x_{441} &\le 1 &&(2/8)\\ x_{513} + x_{522} + x_{531} &\le 1 &&(1/8)\\ x_{612} + x_{621} &\le 1 &&(0)\\ \end{align} For example, the first constraint enforces that at most one number with a 1 in the units digit can be selected.

We also have optimal dual multipliers for the lower bounds $x_j \ge 0$ as follows: \begin{align} -x_{117} &\le 0 &&(2/8) \\ -x_{126} &\le 0 &&(1/8) \\ -x_{171} &\le 0 &&(1/8) \\ -x_{216} &\le 0 &&(1/8) \\ -x_{711} &\le 0 &&(1/8) \\ \end{align}

Adding up the inequalities with the corresponding dual multipliers shows that $\sum_{j \in S} x_j \le 5$.