Counting will really take loooong!

How many 4 4 -digit integers (from 1000 1000 to 9999 9999 ) have at least one digit repeated?

This problem is not original.


The answer is 4464.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Mahdi Raza
Jul 4, 2020

The total numbers are:

Total such numbers = 9999 1000 + 1 = 9000 \green{\text{Total such numbers }} = 9999-1000+1 = 9000

We can count the numbers which have No digit repeated as follows

No digit repeated = 9 1st digit 0 × 9 × 8 × 7 The order follows = 4536 \orange{\text{No digit repeated }} = \underbrace{9}_{\text{1st digit } \ne 0} \times \underbrace{9 \times 8 \times 7}_{\text{The order follows}} = 4536

Using the inclusion-exclusion principle:

Total such numbers = No digit repeated + At least one digit repeated 9000 4536 = At least one digit repeated 4464 = At least one digit repeated \begin{aligned} \green{\text{Total such numbers }} &= \orange{\text{No digit repeated }} + \blue{\text{ At least one digit repeated}} \\ \green{9000} - \orange{4536} &= \blue{\text{ At least one digit repeated}} \\ \boxed{4464} &= \blue{\text{ At least one digit repeated}} \end{aligned}

Brilliant solution! BTW, what is inclusion-exclusion principle? I understand what you mean. but what is its formal definition?

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

It is a very famous technique in combinatorics... here see this link. I think i should add this in the explanation as well. You might hear it as PIE later

Mahdi Raza - 11 months, 1 week ago

Log in to reply

Thanks! I'll see to it tomorrow, but I will upvote your colorful solution today only. Your solutions mostly contain something which I never heard. Although I forget some, they make me learn a lot! Keep it up!

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

@Vinayak Srivastava Thank you for your general appreciation. It matters a lot. BTW If you are preparing for PRMO, this might come very handy in general. This isn't a hi-fi concept, just a formally stated definition that is very useful

Mahdi Raza - 11 months, 1 week ago

Log in to reply

@Mahdi Raza Ok, thanks a lot!

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

@Vinayak Srivastava You're most welcome!!

Mahdi Raza - 11 months, 1 week ago

I realized it has the same formula which I had to mug up for exam:

n ( A B ) = n ( A ) + n ( B ) n ( A B ) n(A\cup B)=n(A)+n(B)-n(A\cap B)

Rest of the things went above my head! :)

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

Is there anything you would like me to simplify or breakdown

Mahdi Raza - 11 months, 1 week ago

Suppose in your class 50% students like dancing , 30% students like singing and 20% students like both singing as well as dancing.Now, what is the total percent of students who likes either dancing or singing??So,to solve this, we have to find the student who only likes singing(30%-20%=10%) and dancing (50%-20%=30%),therefore answer will only singers + only dancer + both singer as well as dancer = 60%

And,the formula is saying same thing

50%+30%-20%=60%

Hope it helps!!!

A Former Brilliant Member - 11 months, 1 week ago

You are in 9th right, so this formula of set theory comes in 11th if I am right...

Mahdi Raza - 11 months, 1 week ago

Log in to reply

In which class do you read bro??

A Former Brilliant Member - 11 months, 1 week ago

No problem @Mahdi Raza and @Kriti Kamal ! I have understood this formula, I read a little from my book and I can understand. But, the rest of the equations in that wiki just went above my head :) I don't want to disturb you because I am slow at learning, so please don't waste your time! Thanks for asking! Also @Kriti Kamal , your explanation is also good! Thanks!

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

@Vinayak Srivastava PIE is mostly taught in 11th in India. But the formula you are referring n(A∪B)=n(A)+n(B)−n(A∩B) is actually related to this only which you might have learnt in 9th. Basically what @Mahdi Raza means is that if I know the total no. of 4-digit no.s and I know that how many no.s are those in which no digit is repeated it means simply the rest no.s are the ones in which at least 1 digit is repeated. n(A∪B)=n(A)+n(B)−n(A∩B) simply means that if I have two sets or categories and I want to know the union or total no. of things in set A and set B, then I simply add them to get their total however if some things are common in A and B they will get counted twice so to add them only once we subtract the common things once which is represented by n(A∩B). If there are no things in common then n(A∩B) is 0 which means the total of A and B is just n(A∪B)=n(A)+n(B).

Siddharth Chakravarty - 11 months, 1 week ago

Log in to reply

@Siddharth Chakravarty Yes, and these two sets here are disjoint. Meaning there is no such number which “does not have any repeated digit” and have “at least 1 digit repeated”

Mahdi Raza - 11 months, 1 week ago

Log in to reply

@Mahdi Raza Yes therefore n(A∩B) =0. They are also referred to as mutually exclusive sets.

Siddharth Chakravarty - 11 months, 1 week ago

Log in to reply

@Siddharth Chakravarty Oh, so this is what mutually exclusive means! Thank you!

Vinayak Srivastava - 11 months, 1 week ago

Log in to reply

@Vinayak Srivastava Yes mutually exclusive is something in which one thing prevents the other from happening the same thing. In this case if in a number it has no digits repeated then it prevents this no. being included in the set of no.s in which atleast 1 digit is repeated. Mutually means understanding together or in the same way and exclusive means removing or not admit. So mutually exclusive means agreeing and understanding together thus to remove one element from another.

Siddharth Chakravarty - 11 months, 1 week ago

@Mahdi Raza ,same method.

A Former Brilliant Member - 11 months, 1 week ago

Log in to reply

@Kriti Kamal , Great!

Mahdi Raza - 11 months, 1 week ago
Razing Thunder
Jul 7, 2020
1
2
3
4
5
6
a=0
for i in range(1000,10000):
    z=str(i)
    if z[0]==z[1] or z[0]==z[2] or z[0]==z[3] or z[1]==z[2] or z[1]==z[3] or z[2]==z[3] :
        a+=1
print(a)        

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...