Number of positive integers which have no two digits having the same

Question

Number of positive integers which have no two digits having the same value with sum of their digits being 45, is

(A) 10! 
(B) 9*9!
(C) 17*8! 
(D) 9!
(E) 8!

Are You Up For the Challenge: 700 Level Questions: 700 Level Questions

gmatcafe · Answer

If no two digits should have the same value, we can use each digit from 0 to 9 once only. Only sum of all these digits equals to 45. So our numbers should contain a) all digits from 0 to 9 or b) all digits from 1 to 9.
a) 10 digit number: We can form 10!different numbers using the digits from 0-10.
However, first digit cannot be 0 and 10! includes numbers whose digit is 0.
In order to exlude these numbers we subtract the number of numbers whose 1st digit is 0.
So actually we can form 10!-9! different numbers from these 10 digits.
b) 9-digit numbers: We can make 9! different numbers using these 9 digits.
In total we can form 10!-9!+9!=10! different numbers.
IMO answer is A)

OnePieceIsReal · Answer

This is the first time I am giving a solution to a problem, pls correct me if I am wrong
as the digits must not repeat and also the sum of digits is 45,

If we add the digits 0-9, the sum is 45, thus all the digits can be used therefore, no of ways of forming digits-
For first digit- 10 ways
For 2nd-9 ways
For 3rd-8 ways
For 4th- 7 thus upto last will be 1, multiplying all give us 10¡ as answer.

egmat · Answer

Hi OnePieceIsReal,

Welcome, and since you asked to be corrected, there is a small mistake here:  your answer is right, but the road you took to it isn't.  That deserves more of your attention than a wrong answer would, because a method that accidentally works is a method you'll trust again.

Your first move is the real insight, though. Since 0+1+2+...+9 =  45 , the digits have to sum to the whole set. Hold onto that.

The correct route, in two steps

Step 1 - find every digit set that sums to 45.  There are  two , not one. The full set {0,1,...,9} sums to  45 , and so does {1,2,...,9}, because dropping the  0  costs nothing. Remove any other digit and the sum falls short. So two families of numbers qualify.

Step 2 - count each family, and never let 0 lead.

- Using all ten digits: total arrangements are  10! , but the ones with  0  in front aren't 10-digit numbers at all. Fix 0 in the lead and arrange the other nine:  9!  of those. Valid count =  10! - 9! .
- Using {1,...,9}: no 0 in the pool, so every arrangement is a legal 9-digit number:  9! .

Total = (10! - 9!) + 9! =  10! , choice  A .

Why your two mistakes hid each other

You counted the leading-zero strings you should have discarded, and you skipped the 9-digit family you should have added. Each group has exactly  9!  members, and that's no coincidence: take any discarded string, delete its leading 0, and what's left  is  one of those 9-digit numbers. One-to-one, both directions. Your two errors were the same size, so they cancelled and the total still read 10!.

The habit to build

Whenever  0  sits in your digit pool, one question comes first, every time:  can 0 take the lead?  Quick test - how many  2-digit  numbers use each of {0, 1} exactly once? It looks like 2x1 =  2 , but 01 is just 1. Only  10  qualifies, so the answer is  1 .

Your instinct on the digit sum was excellent. Now make that leading-zero check automatic.

Answer: A

OnePieceIsReal · Answer

I have a doubt, why zero cannot be in the lead, since we don’t have the condition of the no. Of digits to be fixed, so in the case where zero will be in lead will simply be unique 9 digit numbers while where zero is not in lead will be 10 digit numbers.

Bunuel · Answer

A leading zero does not create a different number. For example, 0123456789 is simply 123456789. No one writes an integer with a leading zero.

egmat · Answer

Hi OnePieceIsReal, your reasoning in this post is correct, and it is actually a cleaner route than the two-family count I posted earlier. Let me confirm it and then name the one condition it rests on.

Bunuel's line above is the same fact you started from: 0123456789 is not a new ten-digit number, it is just 123456789. Where your post goes further is in seeing what that means for the  count . Because the question never fixes how many digits the number must have, the leading-zero arrangements are not waste. They are the nine-digit numbers built from {1, ..., 9}.

Why your total and mine have to agree.  Take all 10! arrangements of {0, 1, ..., 9} and split them in two:
 
 0 not in front: these are 10! - 9! genuine ten-digit numbers. 
 0 in front: 9! strings, and deleting the leading 0 turns each one into a nine-digit number from {1, ..., 9}. Every such nine-digit number shows up exactly once this way, so nothing is double counted and nothing is missed.  
So the 10! arrangements line up one-to-one with the numbers the question asks for. My earlier post counted the same two families separately and added them, (10! - 9!) + 9! = 10!. Your route and mine are the same count read in two different orders.

The condition to hold onto.  Your slot count (10 choices for the first digit, then 9, then 8, and so on) is safe here only because the length is free. Suppose the question had asked for  ten-digit  numbers with distinct digits summing to 45. Then the leading-zero strings would have to be thrown out with nothing to add back, and the answer would be 10! - 9!, not 10!. Same digits, same sum, different count.

So the habit is one question, asked before you count: is the number of digits fixed? If it is, leading zeros are simply discarded. If it is not, ask what shorter numbers they become, exactly as you did here.

Well spotted.

Number of positive integers which have no two digits having the same

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

Number of positive integers which have no two digits having the same

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards