MathDB
Problems
Contests
National and Regional Contests
India Contests
Chennai Mathematical Institute B.Sc. Entrance Exam
2018 CMI B.Sc. Entrance Exam
5
5
Part of
2018 CMI B.Sc. Entrance Exam
Problems
(1)
CMI 2018 #5
Source: CMI 2018
8/31/2018
An
alien
\textrm{alien}
alien
script has
n
n
n
letters
b
1
,
b
2
,
…
,
b
n
b_1,b_2,\dots,b_n
b
1
,
b
2
,
…
,
b
n
. For some
k
<
n
/
2
k<n/2
k
<
n
/2
assume that all words formed by any of the
k
k
k
letters (written left to right) are meaningful. These words are called
k
k
k
-words. Such a
k
k
k
-word is considered
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
b
o
l
d
′
>
s
a
c
r
e
d
<
/
s
p
a
n
>
<span class='latex-bold'>sacred</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
b
o
l
d
′
>
s
a
cre
d
<
/
s
p
an
>
if:i. no letter appears twice and, ii. if a letter
b
i
b_i
b
i
appears in the word then the letters
b
i
−
1
b_{i-1}
b
i
−
1
and
b
i
+
1
b_{i+1}
b
i
+
1
do not appear. (Here
b
n
+
1
=
b
1
b_{n+1} = b_1
b
n
+
1
=
b
1
and
b
0
=
b
n
b_0 = b_n
b
0
=
b
n
).For example, if
n
=
7
n = 7
n
=
7
and
k
=
3
k = 3
k
=
3
then
b
1
b
3
b
6
,
b
3
b
1
b
6
,
b
2
b
4
b
6
b_1b_3b_6, b_3b_1b_6, b_2b_4b_6
b
1
b
3
b
6
,
b
3
b
1
b
6
,
b
2
b
4
b
6
are sacred
3
3
3
-words. On the other hand
b
1
b
7
b
4
,
b
2
b
2
b
6
b_1b_7b_4, b_2b_2b_6
b
1
b
7
b
4
,
b
2
b
2
b
6
are not sacred. What is the total number of sacred
k
k
k
-words? Use your formula to find the answer for
n
=
10
n = 10
n
=
10
and
k
=
4
k = 4
k
=
4
.
combinatorics
recursions