MathDB
Problems
Contests
National and Regional Contests
India Contests
Chennai Mathematical Institute B.Sc. Entrance Exam
2023 CMI B.Sc. Entrance Exam
4
4
Part of
2023 CMI B.Sc. Entrance Exam
Problems
(1)
Results on n students with distinct heights
Source: CMI 2023 B4
5/9/2023
In a class there are n students with unequal heights.
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
b
o
l
d
′
>
(
a
)
<
/
s
p
a
n
>
<span class='latex-bold'>(a)</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
b
o
l
d
′
>
(
a
)
<
/
s
p
an
>
Find the number of orderings of the students such that the shortest person is not at the front and the tallest person is not at the end.
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
b
o
l
d
′
>
(
b
)
<
/
s
p
a
n
>
<span class='latex-bold'>(b)</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
b
o
l
d
′
>
(
b
)
<
/
s
p
an
>
Define the badness of an ordering as the maximum number
k
k
k
such that there are
k
k
k
many people with height greater than in front of a person. For example: the sequence
66
,
61
,
65
,
64
,
62
,
70
66, 61, 65, 64, 62, 70
66
,
61
,
65
,
64
,
62
,
70
has badness
3
3
3
since there are
3
3
3
numbers greater than
62
62
62
in front of it. Let
f
k
(
n
)
f_k(n)
f
k
(
n
)
denote the number of orderings of
n
n
n
with badness
k
k
k
. Find
f
k
(
n
)
f_k(n)
f
k
(
n
)
. (Hint: Consider
g
k
(
n
)
g_k(n)
g
k
(
n
)
as the number of orderings of n with badness less than or equal to
k
k
k
)
combinatorics
CMI