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"

(→‎Solution)
(→‎Problem)
 
(One intermediate revision by one other user 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==
−
Assume AB, AC, and AD are all rail.
+
Assume <math>AB</math>, <math>AC</math>, and <math>AD</math> are all rail.
  
−
None of BC, CD, or CD can be rail, as those cities would form a rail triangle with A.
+
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 BC is bus, then BD is bus as well, as otherwise B has all three types.
+
If <math>BC</math> is bus, then <math>BD</math> is bus as well, as otherwise <math>B</math> has all three types.
  
−
However, CD cannot be rail (as 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).
+
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.
 
Therefore, no city can have three connections of the same type.
  
  
−
Assume there are 5 towns - A, B, C, D, and E.
+
Assume there are 5 towns - <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>, and <math>E</math>.
  
−
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.
+
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 AB and AC be rail connections, and AD and AE be bus.
+
Let <math>AB</math> and <math>AC</math> be rail connections, and <math>AD</math> and <math>AE</math> be bus.
  
−
Assume CD is air.
+
Assume <math>CD</math> is air.
  
−
BC cannot be rail (ABC would be a rail triangle) or bus (C would have all three types), so BC must be 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.
  
−
DE cannot be bus (ADE would be a bus triangle) or rail (D would have all three types), so DE 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.
  
−
BE cannot be rail (E would have all three types) or bus (B would have all three types), so BE 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, 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).
+
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 CD is air is false.
+
Therefore, the assumption that <math>CD</math> is air is false.
  
−
CD can equally be rail or bus; assume it is bus.
+
<math>CD</math> can equally be rail or bus; assume it is bus.
  
−
BC cannot be rail (ABC would be a rail triangle) or air (C would have all three types), so BC must be 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.
  
−
BD cannot be air (B would have all three types) or bus (D would have three bus connections), so BD must be rail.
+
<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.
  
−
DE cannot be air (D would have all three types) or bus (D would have three bus connections), so DE 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.
  
−
CE cannot be air (C would have all three types) or bus (E would have three bus connections), so CE 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 BE, which cannot be orange as both B and D would have all three types, but this means there are no air connections.
+
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.
 
Therefore, it is impossible with five (or more) towns.
Line 49: Line 49:
 
A four-town mapping is possible:
 
A four-town mapping is possible:
  
−
AB, BC, CD, and DA are connected by bus
+
<math>AB</math>, <math>BC</math>, <math>CD</math>, and <math>DA</math> are connected by bus.
  
−
AC is connected by rail
+
<math>AC</math> is connected by rail.
  
−
BD is connected by air
+
<math>BD</math> is connected by air.
  
−
Therefore, the maximum number of towns is 4.
+
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"