I submitted a problem to brilliant which was unfortunately rejected. I thought it would be nice to share it with all of you. Here it is : \[\] \(\small 7\)-digit numbers (without repetition of digits) are formed using the digits \( \small \{1,2,3,4,5,6,7 \} \). Let \(\small S\) be the set of all such numbers. How many pairs of \(\small (a,b) \in S \) exist such that \(b\) is a multiple of \(a\) given that \( \small a \neq b\)

## Comments

Sort by:

TopNewestEvery number is of the form 9x+1, and since the max we can multiply \(a\) is by 7, there are no such numbers. Nice problem. – Peiyush Jain · 3 years, 5 months ago

Log in to reply

– Vikram Waradpande · 3 years, 5 months ago

Yeah I had the same solution. All numbers are \(1\) mod \(9\). And \( \large \frac{b}{a} \small < 7 \). So basically there cannot exist another number that is \(1\) mod \(9\)Log in to reply

– Peiyush Jain · 3 years, 5 months ago

Did they give you a reason for rejection?Log in to reply

– Vikram Waradpande · 3 years, 5 months ago

They said it did not fit in any of the problem categories.Log in to reply

– Peiyush Jain · 3 years, 5 months ago

I see. Thanks.Log in to reply

This is basically a case checking:

We can have the multiples in the range \( [2,7] \)

When the multiple is \(2\) it is not possible, because when you multiply \(4\)[in the number] and \(2\) , the resulting digit can be either \(8\) or \(9\) [The greatest carry over can be only \(1\) ].

When the multiple is \(3\), the digit \(6\) when multiplied by \(3\) can only give either \(8,9,0\) which is again not possible.

When the multiple is \(4\), the digit \(2\) in the number when multiplied will produce the corresponding digit \(8,9,0\) since highest carry over is \(2\). This is also not possible.

When it is \(5\): Now notice that the \(1 \times 5=5\), \(3 \times 5\) gives us another digit \(5\) in the multiplication of the the \(7\) digit number. Also \(7 \times 5 \) gives us the same.Also \(5 \times 5\) gives us another \(5\) to deal with. Now out of these we need one of them to stay \(5\) and other to either become \(6\) or \(7\). But, the other if it is distinct from other numbers will exceed \(7\). So no numbers here either.

When it is \(6\):

\(1 \times 6\) and \(6 \times 6\) gives us \(6\).

So to preserve non-repetition, on one has to be \(6\) and the other \(7\).

First note the first digit of \(a\) has to be \(1\) or our multiple will be out of the domain. This implies that the last digit has to be \(6\) [carry over concept].

So, if a pair exists in this case, then \(a\) has to have \(1\) in the first place and \(6\) in the last.

Now the second last digit that can survive[stay in our range] the carry over \(3\) derived from the last digit is either \(2\) or \(3\). If it is \(2\) then the number next to \(1\) can only be \(3\) since \(3 \times 6\) will gives us a carry over \(1\). But, wait the other numbers left [\(4,5,7\) ] will ensure this does not happen.

So, the number before \(6\) can be \(3\) and the number after \(1\) has to be \(2\).

The digit before \(3\) cannot be \(7\) because the numbers to be placed before \(7\) are only \(5\) or \(4\). If it is \(5\) we have a repetition of the digit \(4\) and if the digit before 7 is 4, then we have an \(8\) in the resulting digit. So, \(7\) must come after \(2\). Great, this is not possible since that will make our 2nd digit of \(b\) as \(6\), but \(6\) is already the last digit.

Now when the multiple is \(7\) : It is obviously not possible since the first digit will be greater than \(8\) no matter how you place the digits.

There might be some parts that are incoherent, and I might have easily missed something, in any case let me know if the answer to the question is not \(0\). – Aditya Parson · 3 years, 5 months ago

Log in to reply

– Vikram Waradpande · 3 years, 5 months ago

The answer is correct and I like the solution as well!Log in to reply