5
$\begingroup$

Hello, everyone!

I received the following question as part of my Discrete Mathematics course and am unable to solve it.

How many strings of four decimal digits that do not contain the same digit three times?

I know that it is related to counting rules and involves the product and sum rules however, I can not decide what approach to take to solve.

What I have so far: 1) Solution 1 Total number of combinations = 10 * 10 * 10 * 10 = 10 ^ 4 = 10 000

Number of combinations where the string contains the same digit three times: 1 * 1 * 1 * 10 = 10 * 10 (since 0 - 9 are possible numbers that can be repeated) = 100

Number of combinations where the string does not contain the same digit three times: 10 000 - 100 = 9 900

Help Needed: I do not know if this is correct. If it isn't, I would be very appreciative if someone could direct me to the correct method for solving the problem.

$\endgroup$
  • 2
    $\begingroup$ This isn't correct, because you're not taking digit positions into account. You could start by writing down all of the numbers with four digits that contain at least three $9$s. $\endgroup$ – Eric Tressler May 18 '16 at 5:41
  • 1
    $\begingroup$ By the way, your question has 892 characters, as many as 223 4-digit numbers -- it would have been easier to just check. $\endgroup$ – Eric Tressler May 18 '16 at 5:47
  • 1
    $\begingroup$ You only took into consideration numbers of the form $aaab $ but what about $aaba, \; abaa, \; aaaa, \;baaa $ $\endgroup$ – alpastor May 18 '16 at 5:51
5
$\begingroup$

As Eric noted in a comment, you're not taking into account the fact that there are four different positions for the fourth digit. The correct calculation is

$$ 10^4-4\cdot10\cdot10+3\cdot10=9630\;, $$

where the last term corrects for the fact that the second term counts each string of four identical digits $4$ times. Alternatively, not counting them in the second term, you could also write

$$ 10^4-4\cdot10\cdot9-10=9630\;. $$

$\endgroup$
5
$\begingroup$

Bad strings with exactly $3$ digits same:

[Choose triple]$\;\times\;$[Choose single]$\;\times\;$ [Place single] $=\binom{10}{1}\binom91\times 4 = 360$

Bad strings with all $4$ digits same: = $10$

Depending upon whether you mean exactly $3$ same or at least $3$ same,
answers are $9640$ or $9630$

$\endgroup$
  • $\begingroup$ I like that this answer calls into question the definition itself. I'm not a mathematician, but in all areas of both business and science I've had problems where a simple lack of definitions were major roadblocks to formulating solutions. $\endgroup$ – corsiKa May 18 '16 at 16:04
  • 1
    $\begingroup$ @corsiKa: An apocryphal quote from Einstein: If I had only one hour to save the world, I would spend $55$ minutes defining the problem and $5$ minutes solving it ! $\endgroup$ – true blue anil May 18 '16 at 17:33
3
$\begingroup$

the possible combinations are

axxx-10*9=90

xaxx-10*9=90

xxax-10*9=90

xxxa-10*9=90

xxxx-only 10 times

a can be 0 to 9

so total=10000-370=9630

$\endgroup$
  • $\begingroup$ You need to explain your answer. $\endgroup$ – Emre May 18 '16 at 7:15
2
$\begingroup$

I think it should work somehow as foollows: There are $10\cdot9\cdot8\cdot7=5040$ strings where all digits are different and there are $10\cdot(1\cdot1\cdot9\cdot8)\cdot\binom{4}{2}=4320$ where exactly one digit appears twice (the expression is constrcted in the following way: choose one of the ten digits, this digit is chosen twice and the other two digits are chosen randomly without replacement, but there are six ways to of the two equal digits in a string of four). It remains to include the strings that contain two pairs of digits each. This gives $10\cdot9\cdot\binom{4}{2}\cdot\frac{1}{2}=270$, because there are $10\cdot9$ ways in which we can pick two numbers and then it remains to choose the different positions in which we can put two of the digits in the string. The last division accounts for the fact that each permutation is chosen twice. This gives a total of 9630 different strings.

$\endgroup$
  • 2
    $\begingroup$ This is good, except you shouldn't add the $10$ with four digits equal, because they contain the same digit three times. (At least that's how I understand "contain the same digit three times" without "exactly" in it.) Your result $9630$ anyway doesn't include the $10$. $\endgroup$ – joriki May 18 '16 at 6:10
  • $\begingroup$ That's correct. Thanks. I will edit the answer, so as not to mislead. $\endgroup$ – Nikolas May 18 '16 at 6:12
0
$\begingroup$

Starting with the maximum number of 4 digit combinations, you'll have 10,000 possibilities.

Now lets look at how we can combine a single digit 3+ times within that 4 digit number:

DXXX * 9 different values of D where D != X
XDXX * 9
XXDX * 9
XXXD * 9
XXXX * 1

So that is 37 different combinations. Now 37 * 10 different digits = 370 ways to make a digit appear at least 3 times.

Therefore, 10,000 - 370 = 9630 4 digit numbers where the same digit does not appear 3 times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.