Permutations of divisible integers
Problem Statement:
How many integers between 100 and 999, inclusive have the property that some permutation of its digits is a multiple of 11 between 100 and 999? For example , both 121 and 211 has this property.
Options:
a) 226
b) 243
c) 270
d) 469
e) 486
Solution:
This is an amazing problem and requires extensive thinking for different cases. Let's simplify the problem a bit, we need to find all the multiples of 11 between 100 and 999 and their different permutations. Now first look at it generally, we have a total of floor(899/11) = 81 multiples of 11 starting from 110 all the way upto 990 and one may think that there are three digits, hence there will be 3! = 6 ways to arrange each number hence we can get 81*6 = 486 (d) option, but this is terribly wrong, because there might be a case in which 2 digits may repeat for example 121, here we have only 3 ways to arrange digits, also a number containing 0 must not permuted so that 0 comes in the first place for example 803 must not be permuted as 038 or 083 because then it becomes a 2 digit number which does not lie between 100 and 999.
So, we need to analyse this problem for these problem causing cases:
Before going to the problem let's have in our mind how to test if a number is divisible by 11 or not, we just need to sum the alternate digits and subtract those two sums
Case 1: 0 is present at the end
The format for such number will be xx0, and we will get 9 cases-----(1) 110, 220, 330, 440, 550, 660, 770, 880 and 990 i.e x varies from [1,9] because for a number to be divisible by 11 a+0-b = 0 , hence a=b.
Now we have 3!/2! = 3 ways to arrange but in one case 0 comes at the front hence we got 2 cases per number.
So total no. of possible cases = 2*9 = 18 -----(i).
Case 2: 0 is present in between the numbers
The format for such number will be a0b, where we have to choose a and b such that they satisfy the divisibility criteria, also numbers with a=b has already been covered in Case1,
now as the sum of a and be should be divisible by 11, we can have (a,b) as (2,9) (3,8) (4,7) (5,6) (6,5) (7,4) (8,3) and (9,2)
So total of 8 cases -----(2) but effectively we have only 4 cases because last four cases can be obtained from the permutation of the first four and there will be 3! = 6 ways to shuffle these number but there will be 2 cases in which 0 will come at first for example 029 and 092 so effectively we get 6-2=4 cases per number.
So total number of possible cases = 4*4 = 16 -----(ii).
Case 3: First and last digits are same and middle one is different
The format for such number will be aba where we have to choose a and b such that they satisfy the divisibility criteria, we will put the values of b and then see what happens to a,
if b = 1, we need to pass a = 6 because 6+6-1 = 11, hence divisible by 11
if b = 2, we need to pass a = 1 because 1+1-2 = 0 , hence divisible by 11
if b = 3, we need to pass a = 7 because 7+7-3 = 11, hence divisible by 11
if b = 4, we need to pass a = 2 because 2+2-4 = 0 , hence divisible by 11
if b = 5, we need to pass a = 8 because 8+8-5 = 11, hence divisible by 11
if b = 6, we need to pass a = 3 because 3+3-6 = 0 , hence divisible by 11
if b = 7, we need to pass a = 9 because 9+9-7 = 11, hence divisible by 11
if b = 8, we need to pass a = 4 because 4+4-8 = 0 , hence divisible by 11
and b cannot be equal to 9 because we cannot pass a as 10.
So in total we have 8 cases -----(3).
Now these combinations can be shuffled in 3!/2! = 3 ways.
So total number of possible cases = 8*3 = 24 -----(iii).
So all the problematic cases has been taken care of but from 100 to 999 we have a total of 81 cases out of which we have worked out with all the numbers with two digits as same and hence we are left with cases in which all three digits are different, hence:
Case 4: All digits are different
The format of such number will be abc, to make things easy we can subtract the cases we already taken care of i.e (1) + (2) + (3) = 25
Hence we are left with 81-25 = 56 combinations in which all a,b,c are different and divisible by 11.
Now what happens when a and c are flipped? for example take 132 and 231 these both will give same permutations and same can be said for every such number so effectively we have 56/2 = 28 numbers and for each number we can have 3! = 6 ways to shuffle,
So total number of possible cases = 28*6 = 168 ----- (iv).
Now summing up all the permutations we have our final answer as (i) + (ii) + (iii) + (iv) = 18 + 16 + 24 + 168 = 226.
Hence option (a) is correct.
This question was asked in AMC 2017, hope you guys liked this article, have a nice day!