Waste less time on Facebook — follow Brilliant.

A nice problem!

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\)

Note by Vikram Waradpande
4 years, 2 months ago

No vote yet
0 votes


Sort by:

Top Newest

Every 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 - 4 years, 2 months ago

Log in to reply

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\)

Vikram Waradpande - 4 years, 2 months ago

Log in to reply

Did they give you a reason for rejection?

Peiyush Jain - 4 years, 2 months ago

Log in to reply

@Peiyush Jain They said it did not fit in any of the problem categories.

Vikram Waradpande - 4 years, 2 months ago

Log in to reply

@Vikram Waradpande I see. Thanks.

Peiyush Jain - 4 years, 2 months ago

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 - 4 years, 2 months ago

Log in to reply

The answer is correct and I like the solution as well!

Vikram Waradpande - 4 years, 2 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...