Combinatorial

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Combinatorial

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: RMO 2007 problem

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

47 posts

#1 h Oct 10, 2007, 4:56 PM • 1 Y

Y by Adventure10

How many 6-digit numbers are there such that-:
a)The digits of each number are all from the set $\{1,2,3,4,5\}$
b)any digit that appears in the number appears at least twice ?
(Example: $225252$ is valid while $222133$ is not)
[weightage 17/100]

This post has been edited 1 time. Last edited by bluecarneal, Sep 15, 2017, 11:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

117 posts

nktp

#2 h Oct 11, 2007, 2:10 AM • 2 Y

Y by Adventure10, Mango247

Sorry if it isn't exactly!
1) Number consist $1$ digit appear $6$ times: $5$ number
2) Number consist $2$ digit $a,b$ which $a$ appear $4$ times, $b$ appear $2$ times: $2.C_5^2.C_6^4 = 300$ number
3) Number consist $2$ digit $a,b$ which $a,b$ appear $3$ times: $C_5^2.C_6^3 = 200$ number
4) Number consist $3$ digit $a,b,c$ which $a,b,c$ appear $2$ times: $C_5^3.C_6^2.C_4^2 = 900$ number
Sum: $1405$ number

This post has been edited 1 time. Last edited by nktp, Oct 11, 2007, 9:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

47 posts

#3 h Oct 11, 2007, 8:57 AM • 2 Y

Y by Adventure10, Mango247

nktp wrote:

Sorry if it isn't exactly!
1) Number consist $1$ digit appear $6$ times: $5$ number
2) Number consist $2$ digit $a,b$ which $a$ appear $4$ times, $b$ appear $2$ times: $C_5^2.C_6^4 = 150$ number
3) Number consist $2$ digit $a,b$ which $a,b$ appear $3$ times: $C_5^2.C_6^3 = 200$ number
4) Number consist $3$ digit $a,b,c$ which $a,b,c$ appear $2$ times: $C_5^3.C_6^2.C_4^2 = 900$ number
Sum: 1255 number

shouldnt the second case be multiplied by 2 ? For onr digit may appear 4 and other twice, or vice versa ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

117 posts

nktp

#4 h Oct 11, 2007, 9:58 AM • 1 Y

Y by Adventure10

OK! I too hurry! Case 2 be $a$ appear $4$ , $b$ appear $2$ and $a$ appear $2$ , $b$ appear $4$ , it have $300$ number and total is $1405$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

47 posts

#5 h Oct 12, 2007, 4:15 PM • 2 Y

Y by Adventure10, Mango247

i did this by another approach,could some1 plz tell whats the error i am making
let there be 6 slots then the first slot can be filled in 5 ways, the next in one way(since the digit is supposed to repeat) the next in 4,1,3,1 So the total possible ways are $5\times 4\times 3\times \frac {6!}{2!.2!.2!}$ as there are three pairs of two digits each. This gives $5400$ which is too big in my opinion. (There are other cases also but i think i am going wrong here itself)
Could some1 plz help

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

117 posts

nktp

#6 h Oct 12, 2007, 5:00 PM • 1 Y

Y by Adventure10

I thinks if you do by this way then if you select example $1$ in first step, $2$ in third step and $3$ in fifth step is difference with the way that you select example $1$ in first step, $3$ in third step and $2$ in fifth step. It is wrong because $2$ this way is same:select $3$ number $1,2,3$ , then change place $3$ this number (you count $\frac {6!}{2!.2!.2!}$ is number of way to change place $3$ couple this number)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#7 h Sep 15, 2020, 6:09 AM

Y by

Call a number $good$ if it satisfies conditions $(a)$ and $(b)$ .
Case 1: The number contains only 1 distinct digit.
No of such $good$ numbers $= 5$
Case 2 : The number consists of exactly 2 distinct digits. By condition $(b)$ there are two possible subcases i.e $(2+4),(4+2)$ and $(3+3)$
Total number of such $good$ numbers
$= \binom{5}{2}( \frac {6!}{2!4!} + \frac {6!}{3!3!} +\frac {6!}{4!2!} )$
$= 10 \cdot ( 15+15+20) = 500$
Case 3 : The number has exactly 3 distinct digits. There is only one option i.e $(2+2+2)$
No of such $good$ numbers $= \binom{5}{3} \cdot \frac{6!}{2!2!2!}$
$= 900$
There can't be more than 3 distinct digits as it violates condition $(b)$ .
Total number of $good$ numbers $= 1405$

This post has been edited 2 times. Last edited by Kuroshio, Sep 16, 2020, 7:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonecoolLovesMaths

3438 posts

SomeonecoolLovesMaths

#9 h May 24, 2025, 8:58 PM

Y by

We will do casework.

Claim: The number cannot have more than $3$ distinct digits.
Proof. Assume the contrary. Then it must have at least $4 \cdot 2 = 8$ digits, which is against our limitations.

Case $1$ : The number has $1$ distinct digits.
Number of such numbers $= \binom{5}{1} \cdot \dfrac{5!}{5!} = \boxed{5}$ .

Case $2$ : The number has $2$ distinct digits.
Now there are $2$ subcases:
Subcase $(i)$ : The number has $4$ of one digit and $2$ of another.
Number of such numbers $= \binom{5}{2} \cdot \dfrac{6!}{4!2!} \cdot 2! = \boxed{150}$ .
Subcase $(ii)$ : The number has $3$ of each digit.
Number of such numbers $= \binom{5}{2} \cdot \dfrac{6!}{3!3!} = \boxed{200}$ .

So total such numbers $= \boxed{350}$ .

Case $3$ : The number has $3$ distinct digits.
Number of such numbers $= \binom{5}{3} \cdot \dfrac{6!}{2!2!2!} = \boxed{900}$ .

So finally the number of such numbers $= \boxed{\textbf{1405}}$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a