Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1981 USAMO Problems/Problem 2"
(→‎Problem)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a trian link. No three towns, <math>A, B, C </math> are such that the links between <math>AB, AC</math> and <math>BC</math> are all air, all bus or all train.
+
What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a train link. No three towns, <math>A, B, C </math> are such that the links between <math>AB, AC</math> and <math>BC</math> are all air, all bus or all train.
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Assume <math>AB</math>, <math>AC</math>, and <math>AD</math> are all rail.
 +
 
 +
None of <math>BC</math>, <math>CD</math>, or <math>CD</math> can be rail, as those cities would form a rail triangle with <math>A</math>.
 +
 
 +
If <math>BC</math> is bus, then <math>BD</math> is bus as well, as otherwise <math>B</math> has all three types.
 +
 
 +
However, <math>CD</math> cannot be rail (as <math>\triangle ACD</math> would be a rail triangle), bus (as <math>BCD</math> would be a bus triangle), or ferry (as <math>C</math> and <math>D</math> would have all three types).
 +
 
 +
Therefore, no city can have three connections of the same type.
 +
 
 +
 
 +
Assume there are 5 towns - <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>, and <math>E</math>.
 +
 
 +
Two connections from <math>A</math> must be of one type, and two of another; otherwise there would be at least three connections of the same type from <math>A</math>, which has been shown to be impossible.
 +
 
 +
Let <math>AB</math> and <math>AC</math> be rail connections, and <math>AD</math> and <math>AE</math> be bus.
 +
 
 +
Assume <math>CD</math> is air.
 +
 
 +
<math>BC</math> cannot be rail (<math>\triangle ABC</math> would be a rail triangle) or bus (<math>C</math> would have all three types), so <math>BC</math> must be air.
 +
 
 +
<math>DE</math> cannot be bus (<math>\triangle ADE</math> would be a bus triangle) or rail (<math>D</math> would have all three types), so <math>DE</math> must be air.
 +
 
 +
<math>BE</math> cannot be rail (<math>E</math> would have all three types) or bus (<math>B</math> would have all three types), so <math>BE</math> must be air.
 +
 
 +
However, <math>BD</math> cannot be rail (<math>D</math> would have all three types), bus (<math>B</math> would have all three types), or air (<math>D</math> would have three air connections).
 +
 
 +
Therefore, the assumption that <math>CD</math> is air is false.
 +
 
 +
<math>CD</math> can equally be rail or bus; assume it is bus.
 +
 
 +
<math>BC</math> cannot be rail (<math>\triangle ABC</math> would be a rail triangle) or air (<math>C</math> would have all three types), so <math>BC</math> must be bus.
 +
 
 +
<math>BD</math> cannot be air (<math>B</math> would have all three types) or bus (<math>D</math> would have three bus connections), so <math>BD</math> must be rail.
 +
 
 +
<math>DE</math> cannot be air (<math>D</math> would have all three types) or bus (<math>D</math> would have three bus connections), so <math>DE</math> must be rail.
 +
 
 +
<math>CE</math> cannot be air (<math>C</math> would have all three types) or bus (<math>E</math> would have three bus connections), so <math>CE</math> must be rail.
 +
 
 +
The only connection remaining is <math>BE</math>, which cannot be orange as both <math>B</math> and <math>D</math> would have all three types, but this means there are no air connections.
 +
 
 +
Therefore, it is impossible with five (or more) towns.
 +
 
 +
 
 +
A four-town mapping is possible:
 +
 
 +
<math>AB</math>, <math>BC</math>, <math>CD</math>, and <math>DA</math> are connected by bus.
 +
 
 +
<math>AC</math> is connected by rail.
 +
 
 +
<math>BD</math> is connected by air.
 +
 
 +
Therefore, the maximum number of towns is <math>4</math>.
  
 
==See Also==
 
==See Also==

Latest revision as of 09:42, 20 April 2023

Problem

What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a train link. No three towns, $A, B, C$ are such that the links between $AB, AC$ and $BC$ are all air, all bus or all train.

Solution

Assume $AB$, $AC$, and $AD$ are all rail.

None of $BC$, $CD$, or $CD$ can be rail, as those cities would form a rail triangle with $A$.

If $BC$ is bus, then $BD$ is bus as well, as otherwise $B$ has all three types.

However, $CD$ cannot be rail (as $\triangle ACD$ would be a rail triangle), bus (as $BCD$ would be a bus triangle), or ferry (as $C$ and $D$ would have all three types).

Therefore, no city can have three connections of the same type.


Assume there are 5 towns - $A$, $B$, $C$, $D$, and $E$.

Two connections from $A$ must be of one type, and two of another; otherwise there would be at least three connections of the same type from $A$, which has been shown to be impossible.

Let $AB$ and $AC$ be rail connections, and $AD$ and $AE$ be bus.

Assume $CD$ is air.

$BC$ cannot be rail ($\triangle ABC$ would be a rail triangle) or bus ($C$ would have all three types), so $BC$ must be air.

$DE$ cannot be bus ($\triangle ADE$ would be a bus triangle) or rail ($D$ would have all three types), so $DE$ must be air.

$BE$ cannot be rail ($E$ would have all three types) or bus ($B$ would have all three types), so $BE$ must be air.

However, $BD$ cannot be rail ($D$ would have all three types), bus ($B$ would have all three types), or air ($D$ would have three air connections).

Therefore, the assumption that $CD$ is air is false.

$CD$ can equally be rail or bus; assume it is bus.

$BC$ cannot be rail ($\triangle ABC$ would be a rail triangle) or air ($C$ would have all three types), so $BC$ must be bus.

$BD$ cannot be air ($B$ would have all three types) or bus ($D$ would have three bus connections), so $BD$ must be rail.

$DE$ cannot be air ($D$ would have all three types) or bus ($D$ would have three bus connections), so $DE$ must be rail.

$CE$ cannot be air ($C$ would have all three types) or bus ($E$ would have three bus connections), so $CE$ must be rail.

The only connection remaining is $BE$, which cannot be orange as both $B$ and $D$ would have all three types, but this means there are no air connections.

Therefore, it is impossible with five (or more) towns.


A four-town mapping is possible:

$AB$, $BC$, $CD$, and $DA$ are connected by bus.

$AC$ is connected by rail.

$BD$ is connected by air.

Therefore, the maximum number of towns is $4$.

See Also

1981 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1981_USAMO_Problems/Problem_2&oldid=192349"