Solu tion
Let the selected course numbers be
k k
k
1
2
151
, , KK
(1)
The 302 numbers consisting of (1) together with
k
k
k
1
2
151
1
1
1
+
+
+
,
, KK
(2)
range in value between 1 and 301. By Pigeonhole principle, at least two of
those values coincide. The numbers (1) are all distinct and so the numbers (2)
are also distinct.
It must be then that one of (1) and one of (2) are equal. Therefore we have
k
k
i
j
=
+1
and course k i follows course k j .
Ì Exam ple 0.1.51: Suppose there are 50 marbles of four different colours
in a sack, if exactly 8 marbles are red, show that there are at least 14 of the
same colour.
Solu tion
If we know that 8 of the marbles are red, then no other marbles could be red,
and we need to partition the rest (50 – 8) = 42 marbles into the rest (4 – 1) = 3
colours.
According to the Pigeon-hole principle, there are at least 42/3 = 14
marbles, which must have the same colour.
0.1.7 Intro duc tion to Gram mar
Grammar is a mechanism to describe the languages.
A grammar (G) is defined as a quadruple
G = (V, T, S, P)
where
V
=
Finite set of objects called VARIABLES
T
=
Finite set of objects called TERMINAL SYMBOLS
S V
∈
=
Start variables
P
=
Finite set of Productions.
A production rule P is of the form
x
y
→
Given a string w, of the form w = uxv, we can use the production rule x
y
→ and
obtain a new string z = uyv.
Introduction
37