Library / /21 of 23

, 2023

Combinatorics Difficulty 4.1 AIME Prove it Canada

A lab has $50$ computers
numbered $1$ through $50$ . Each pair of computers is connected
to each other by a cord. The cords are coloured according to the
following rules.

If the numbers of the two computers are both even or both odd,
then the cord connecting them is red.
Otherwise, the cord connecting them is blue.

A route is a sequence of cords along which data can travel
to get from one computer to another computer within the lab. For
example, data could travel the route from Computer 5 to Computer 12
directly, or the route from Computer 5 to Computer 15 to Computer
12.

There is a route connecting Computer 1 to
Computer $n$ using only red cords. If
$n\neq 1$ , how many possible values
are there for $n$ ?
Show that for every pair of distinct
computers, Computer $A$ and Computer
$B$ , there is always a route between
them that uses only blue cords.
Each red cord and blue cord is removed
and randomly replaced with either a green cord or a yellow cord. Dani
notices that there is no route that connects Computer 1 to Computer 50
that uses only green cords. Show that there is always a route between
Computer 13 and Computer 14 that uses only yellow cords.

Solution

Computer 1 is an odd-numbered computer, and so each cord
connecting Computer 1 to another odd-numbered computer is red.

Thus, there is a route from Computer 1 to each of the odd-numbered
computers from 3 to 49, inclusive, that uses only red cords.

Each cord between an odd-numbered computer and an even-numbered computer
is blue.

Computer 1 is an odd-numbered computer and so every possible route from
Computer 1 to an even-numbered computer must use at least one blue
cord.

Thus there is no route from Computer 1 to any even-numbered computer
that uses only red cords.

There are 24 odd numbers between 2 and 50, and so there are 24 possible
values for $n$ .
Two integers have different parity if one integer is
even and the other is odd.

Two integers have the same parity if they are both even or if
they are both odd.

There are two cases to consider: $A$
and $B$ have different parity, or
they have the same parity.

If $A$ and $B$ have different parity, then the cord
between Computer $A$ and
Computer $B$ is blue, and so there is
a route between them that uses only blue cords.

If $A$ and $B$ have the same parity, then choose a
number $C$ that has different parity
than that of $A$ and $B$ .

The cord between Computer $A$ and
Computer $C$ is blue, and the cord
between Computer $C$ and
Computer $B$ is blue, and so the
route from Computer $A$ to
Computer $C$ to Computer $B$ uses only blue cords.

Thus, for every pair of distinct computers, Computer $A$ and Computer $B$ , there is always a route between them
that uses only blue cords.
If the cord between Computer 13 and Computer 14 is yellow, then
there is a route between them that uses only yellow cords, so assume
that the cord between them is green.

Since there is no route connecting Computer 1 to Computer 50 that uses
only green cords, then the cord between Computer 1 and Computer 50 must
be yellow.

Further, since there is no route connecting Computer 1 to Computer 50
that uses only green cords, then at least one of the following must be
true:

the cord between Computer 1 and Computer 13 is yellow,
or
the cord between Computer 13 and Computer 50 is yellow,

otherwise the route from Computer 1 to Computer 13 to Computer 50
uses only green cords.

Similarly, since there is no route connecting Computer 1 to Computer 50
that uses only green cords, then at least one of the following must be
true:

the cord between Computer 1 and Computer 14 is yellow,
or
the cord between Computer 14 and Computer 50 is yellow,

otherwise the route from Computer 1 to Computer 14 to Computer 50
uses only green cords.

Since at least one of (i) or (ii) must be true, and at least one of
(iii) or (iv) must be true, then there are 4 cases to consider, as
follows.

Case A: (i) and (iii) are true

In this case, the cord between Computer 1 and Computer 13 is yellow,
and the cord between Computer 1 and Computer 14 is yellow, and so the
route from Computer 13 to Computer 1 to Computer 14 uses only yellow
cords.

[[IMAGE0]]

Case B: (i) and (iv) are true

In this case, the cord between Computer 1 and Computer 13 is yellow,
and the cord between Computer 14 and Computer 50 is yellow.

Recall that the cord between Computer 1 and Computer 50 is also yellow,
and so the route from Computer 13 to Computer 1 to Computer 50 to
Computer 14 uses only yellow cords.

[[IMAGE1]]

Case C: (ii) and (iii) are true

In this case, the cord between Computer 13 and Computer 50 is yellow,
and the cord between Computer 1 and Computer 14 is yellow.

Since the cord between Computer 1 and Computer 50 is also yellow, then
the route from Computer 13 to Computer 50 to Computer 1 to Computer 14
uses only yellow cords.

[[IMAGE2]]

Case D: (ii) and (iv) are true

In this case, the cord between Computer 13 and Computer 50 is yellow,
and the cord between Computer 14 and Computer 50 is yellow, and so the
route from Computer 13 to Computer 50 to Computer 14 uses only yellow
cords.

[[IMAGE3]]

Thus, if there is no route that connects Computer 1 to Computer 50
that uses only green cords, then there is always a route between
Computer 13 and Computer 14 that uses only yellow cords.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.