The pigeonhole
principle is one of the simple-minded ideas imaginable, and yet its
generalization involves some of the most profound and difficult results in all
of combinatorial theory.
Pigeonhole Principle:
if there are more pigeons than pigeonholes, then some pigeonhole must contain
two or more pigeons. More generally, if there is k times more pigeons than the
holes, then some pigeonhole must contain at least k+1 pigeons.
Puzzle 1:
There are 15
computers and 10 printers in the office, in every 5minutes a subset of computer
asks for printers. How many different connections are necessary between
computers and printers to guarantee that if 10 (or fewer) computers ask for a
printer, there will always be connections to permit each of these computers to
use a different printer?
Answer:
Very practical
and interesting Problem, I liked it a lot because it kept me busy for an hour,
also when I went for insight of it, I found some interesting constraints which I
will share. If you haven’t found the answer yet, I will suggest you to look into
the puzzle keeping the above principle in mind and try to find out what is the
minimum number of connections that should be there in order to satisfy the
principle without getting into the how exactly the connections will be made. Once
you get that number, I can bet it will take few minutes to find the exact
connections.
There need
to be 60 connections at least by pigeonhole principle. If it’s less than 60
then some printers will have 5 or less connections, so if all the 5 of the
computers have not asked for a printer then that printer will not be used. Hence
we need at least 6 connections per printer. So the now the problem boils down
to can we make 60 connections to achieve the desired result. There are many
solutions possible, following is mine
|
Printer
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
|
Computer
|
1
2
3
4
5
6
|
2
3
4
5
6
7
|
3
4
5
6
7
8
|
4
5
6
7
8
9
|
5
6
7
8
9
10
|
6
7
8
9
10
11
|
7
8
9
10
11
12
|
8
9
10
11
12
13
|
9
10
11
12
13
14
|
10
11
12
13
14
15
|
Aclose look at the table, will reveal that the boundary computers like
computers number 1 and 15 have just 1 connections and the number of connections
keep on increasing for computer numbers towards the center like computer
numbered 6, 7, 8, 9 and 10. We can make a different arrangement where each one
has same number of connections. But I prefer this one because in reality the
usage of resource varies from person to person, so then we can profile them,
and less usage guy can be towards the border and the more usage guy can be
towards the center. Also we can do some randomization for using all the
printers equally during low load conditions.
It’s so
funny how our mind works, with a constraint (the minimum number) and with a definitive
goal it works better. The moment we gave it an approximate number it found out
how to do the connection. It also shows how our brain utilizes the symmetrical
patterns.
In real life
it helps if you can set some definitive goals.
Some more puzzles
if you try to find the diversification of this principle
1. How large a set of distinct numbers
between 1 and n is needed to assure that the set contains a subset of five
equally spaced numbers a1,a2,a3,a4,a5 such that
a2-a1=a3-a2=a4-a3=a5-a4 ?
2. Prove that in a group of 6 people,
there is always a subset of 3 people who either know each other or don’t know
each other. (very interesting)
