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 "1998 AIME Problems/Problem 15"

m (graph theory i suppose belongs under combinatorics? solution by ehehheehee (hope I spelled that right))
m (→‎Solution 2: latex format)
 
(23 intermediate revisions by 7 users not shown)
Line 2: Line 2:
 
Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which <math>(i,j)</math> and <math>(j,i)</math> do not both appear for any <math>i</math> and <math>j</math>.  Let <math>D_{40}</math> be the set of all dominos whose coordinates are no larger than 40.  Find the length of the longest proper sequence of dominos that can be formed using the dominos of <math>D_{40}.</math>
 
Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which <math>(i,j)</math> and <math>(j,i)</math> do not both appear for any <math>i</math> and <math>j</math>.  Let <math>D_{40}</math> be the set of all dominos whose coordinates are no larger than 40.  Find the length of the longest proper sequence of dominos that can be formed using the dominos of <math>D_{40}.</math>
  
−
== Solution ==
+
== Solution 1 ==
 
We can draw a comparison between the domino a set of 40 points (labeled 1 through 40) in which every point is connected with every other point. The connections represent the dominoes.
 
We can draw a comparison between the domino a set of 40 points (labeled 1 through 40) in which every point is connected with every other point. The connections represent the dominoes.
  
Line 9: Line 9:
 
But you can get up to 38 on each segment because you go in to the point then out on a different segment.  Counting going out from the starting and ending at the ending point we have:
 
But you can get up to 38 on each segment because you go in to the point then out on a different segment.  Counting going out from the starting and ending at the ending point we have:
  
−
<math>\frac{38\cdot 40 + 2}2 = 761</math>
+
<math>\frac{38\cdot 38 + 2\cdot 39}2 = \boxed{761}</math>
 +
 
 +
===Clarification===
 +
To clarify the above solution, every time you move to a new vertex, you take one path in and must leave by another path. Therefore every vertex needs to have an even number of segments leaving it (with the exception of the first and last), because the "in" and "out" segments must make a pair.
 +
 
 +
== Solution 2 ==
 +
A proper sequence can be represented by writing the common coordinates of adjacent ordered pairs once. For example, represent (4,7),(7,3),(3,5) as <math>4,7,3,5 .</math> Label the vertices of a regular <math>n</math> -gon <math>1,2,3, \ldots, n .</math> Each domino is thereby represented by a directed segment from one vertex of the <math>n</math> -gon to another, and a proper sequence is represented as a path that retraces no segment. Each time that such a path reaches a non-terminal vertex, it must leave it.
 +
 
 +
 
 +
Thus, when <math>n</math> is even, it is not possible for such a path to trace every segment, for an odd number of segments emanate from each vertex. By removing <math>\frac{1}{2}(n-2)</math> suitable segments, however, it can be arranged that <math>n-2</math> segments will emanate from <math>n-2</math> of the vertices and that an odd number of segments will emanate from exactly two of the vertices.
 +
 
 +
 
 +
In this situation, a path can be found that traces every remaining segment exactly once, starting at one of the two exceptional vertices and finishing at the other. This path will have length <math>\binom{n}{2}-\frac{1}{2}(n-2),</math> which is 761 when <math>n=40</math>.
 +
 
 +
~phoenixfire
 +
=== Note 1 ===
 +
When <math>n</math> is odd, a proper sequence of length <math>\binom{n}{2}</math> can be found using the dominos of <math>D_{n}</math>. In this case, the second coordinate of the final domino equals the first coordinate of the first domino.
 +
 
 +
~phoenixfire
 +
 
 +
== Solution 3 ==
 +
Let <math>A_{n}=\{1,2,3, \ldots, n\}</math> and <math>D_{n}</math> be the set of dominos that can be formed using integers in <math>A_{n} .</math> Each <math>k</math> in <math>A_{n}</math> appears in <math>2(n-1)</math> dominos in <math>D_{n},</math> hence appears at most <math>n-1</math> times in a proper sequence from <math>D_{n}.</math> Except possibly for the integers <math>i</math> and <math>j</math> that begin and end a proper sequence, every integer appears an even number of times in the sequence.
 +
 
 +
 
 +
Thus, if <math>n</math> is even, each integer different from <math>i</math> and <math>j</math> appears on at most <math>n-2</math> dominos in the sequence, because <math>n-2</math> is even, and <math>i</math> and <math>j</math> themselves appear on at most <math>n-1</math> dominos each. This gives an upper bound of
 +
<cmath>
 +
\frac{1}{2}\left[(n-2)^{2}+2(n-1)\right]=\frac{n^{2}-2 n+2}{2}
 +
</cmath>
 +
dominos in the longest proper sequence in <math>D_{n}.</math> This bound is in fact attained for every even <math>n.</math> It is easy to verify this for <math>n=2</math>, so assume inductively that a sequence of this length has been found for a particular value of <math>n</math>.
 +
 
 +
 
 +
Without loss of generality, assume <math>i=1</math> and <math>j=2,</math> and let <math>_{p} X_{p+2}</math> denote a four-domino sequence of the form <math>(p, n+1)(n+1, p+1)(p+1, n+2)(n+2, p+2) .</math> By appending
 +
<cmath>
 +
{ }_{2} X_{4},{ }_{4} X_{6}, \ldots,{ }_{n-2} X_{n},(n, n+1)(n+1,1)(1, n+2)(n+2,2)
 +
</cmath>
 +
to the given proper sequence, a proper sequence of length
 +
<cmath>
 +
\frac{n^{2}-2 n+2}{2}+4 \cdot \frac{n-2}{2}+4=\frac{n^{2}+2 n+2}{2}=\frac{(n+2)^{2}-2(n+2)+2}{2}
 +
</cmath>
 +
is obtained that starts at <math>i=1</math> and ends at <math>j=2 .</math> This completes the inductive proof.
 +
 
 +
 
 +
In particular, the longest proper sequence when <math>n=40</math> is 761.
 +
 
 +
~phoenixfire
 +
 
 +
=== Note 2 ===
 +
In the language of graph theory, this is an example of an Eulerian circuit.
 +
 
 +
~phoenixfire
 +
 
 +
==Solution 4==
 +
Consider the segments joining the vertices of a regular <math>n</math>-gon. For odd <math>n</math>, we see that the number of segments is quite easily <math>\binom{n-1}{2}</math>. This is because every vertex touches every other vertex the same number of times. (<math>\frac{n-1}{2}</math> times to be exact). Hence the answer for odd cases is <math>n\frac{n-1}{2}=\binom{n-1}{2}</math>. (This is because a segment that starts at the first vertex also ends at the first vertex).
 +
For even <math>n</math> however, every vertex touches <math>\frac{n-2}{2}</math> vertices. However, one may be motivated to say that the answer (as in the odd case) is <math>n\frac{n-2}{2}</math>. But this is incorrect, because for the even case, it never ends at the vertex (the first vertex) you started at. So it must end at another vertex. But that vertex has already <math>\frac{n-2}{2}</math> other segments touching it. So we have that the final answer is <math>1</math> plus <math>n\frac{n-2}{2}</math>. The case for <math>n=40</math>, is <math>761</math>.
 +
 
 +
~th1nq3r
 +
 
 +
===Note===
 +
The reason it touches every single other vertex <math>\frac{n-1}{2}</math> for odd <math>n</math> is because there are a total of <math>\binom{n-1}{2}</math> segments, and once dividing <math>\binom{n-1}{2}</math> by <math>n</math>, you will then have the number of segments that are connected to each vertex.
 +
For the even case every vertex has at least <math>\frac{n-2}{2}</math> other segments touching it. This is because (you CAN convince yourself through a painful induction/observation argument, but you probably shouldn't) <math>n</math> is even, and if you try to apply the odd case to the even case, (namely that there is <math>\frac{n-1}{2}</math> segments touching each vertex), there would have to then be <math>n\frac{n-1}{2}</math> total segments, which never works since it never loops back to the vertex you started on). So at LEAST, there should be <math>\frac{n-2}{2}</math> segments touching each vertex. However, there is also at most <math>\frac{n-2}{2}</math> segments touching each vertex. Hence by the (what I call) the "less-than-or-greater-than" argument, there must be <math>\frac{n-2}{2}</math> segments out of each vertex. (Mind the plus one extra vertex since once again, the vertex you started on, it doesn't loop around, so it must end at another vertex). Hence the answer is <math>n\frac{n-2}{2}+1</math>.
 +
 
 +
(I am not very good at explaining things. Sorry if it didn't make sense. Maybe if you find some way to contact me on aops, I could try and help). (For instance, I could see possible confusion at the part where I claim that the minimum lines be <math>\frac{n-2}{2}</math>. You might think, "Oh why not <math>\frac{n-1}{2}-1</math>, or even <math>\frac{n-1}{2}-2</math> or even subtract <math>3</math>?" Well if you actually start off with the fact that there should be at MOST <math>\frac{n-2}{2}</math> segments from each vertex, then it is obvious, since then there must be a minimum of <math>\frac{n-2}{2}</math> segments from each vertex).
 +
 
 +
~th1nq3r
 +
 
 +
== Solution 5 ==
 +
 
 +
We can see that <math>|D_{40}| = 780</math>, since we are choosing 2 integers <math>[1,40]</math>, and order doesn't matter because <math>(i,j)</math> and <math>(j,i)</math> aren't both in the set. Then from doing a smaller example of <math>D_4</math>, we can note that non-endpoints must have an even number of pairs in <math>D</math> in order for one domino's end to match another's beginning. Then, in order to maximize the length we want to minimize the number of dominoes we remove to make all pairs be even (except endpoints). Then we can see that for every two pairs with an odd number of pairs, we can connect single ends to form a circular chain (i.e. if we want to ensure that 2,3 have even pairs then we can imagine (3,1)(1,2)). Thus we can divide 40 by 4 to get the number of numbers to remove. Thus we need to remove 10 numbers. But each number is connected to another, so we remove 20 dominoes. Thus there are 780-20 = 760 dominoes not including endpoints. Finally, we can add one more domino at the end since it doesn't need to match up with the first of another to make it 761.
  
 
== See also ==
 
== See also ==
Line 15: Line 82:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 17:35, 20 June 2024

Problem

Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_{40}$ be the set of all dominos whose coordinates are no larger than 40. Find the length of the longest proper sequence of dominos that can be formed using the dominos of $D_{40}.$

Solution 1

We can draw a comparison between the domino a set of 40 points (labeled 1 through 40) in which every point is connected with every other point. The connections represent the dominoes.

You need to have all even number of segments coming from each point except 0 or 2 which have an odd number of segments coming from the point. (Reasoning for this: Everytime you go to a vertex, you have to leave the vertex, so every vertex reached is equivalent to adding 2 more segments. So the degree of each vertex must be even, with the exception of endpoints) Since there are 39 segments coming from each point it is impossible to touch every segment.

But you can get up to 38 on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have:

$\frac{38\cdot 38 + 2\cdot 39}2 = \boxed{761}$

Clarification

To clarify the above solution, every time you move to a new vertex, you take one path in and must leave by another path. Therefore every vertex needs to have an even number of segments leaving it (with the exception of the first and last), because the "in" and "out" segments must make a pair.

Solution 2

A proper sequence can be represented by writing the common coordinates of adjacent ordered pairs once. For example, represent (4,7),(7,3),(3,5) as $4,7,3,5 .$ Label the vertices of a regular $n$ -gon $1,2,3, \ldots, n .$ Each domino is thereby represented by a directed segment from one vertex of the $n$ -gon to another, and a proper sequence is represented as a path that retraces no segment. Each time that such a path reaches a non-terminal vertex, it must leave it.


Thus, when $n$ is even, it is not possible for such a path to trace every segment, for an odd number of segments emanate from each vertex. By removing $\frac{1}{2}(n-2)$ suitable segments, however, it can be arranged that $n-2$ segments will emanate from $n-2$ of the vertices and that an odd number of segments will emanate from exactly two of the vertices.


In this situation, a path can be found that traces every remaining segment exactly once, starting at one of the two exceptional vertices and finishing at the other. This path will have length $\binom{n}{2}-\frac{1}{2}(n-2),$ which is 761 when $n=40$.

~phoenixfire

Note 1

When $n$ is odd, a proper sequence of length $\binom{n}{2}$ can be found using the dominos of $D_{n}$. In this case, the second coordinate of the final domino equals the first coordinate of the first domino.

~phoenixfire

Solution 3

Let $A_{n}=\{1,2,3, \ldots, n\}$ and $D_{n}$ be the set of dominos that can be formed using integers in $A_{n} .$ Each $k$ in $A_{n}$ appears in $2(n-1)$ dominos in $D_{n},$ hence appears at most $n-1$ times in a proper sequence from $D_{n}.$ Except possibly for the integers $i$ and $j$ that begin and end a proper sequence, every integer appears an even number of times in the sequence.


Thus, if $n$ is even, each integer different from $i$ and $j$ appears on at most $n-2$ dominos in the sequence, because $n-2$ is even, and $i$ and $j$ themselves appear on at most $n-1$ dominos each. This gives an upper bound of \[\frac{1}{2}\left[(n-2)^{2}+2(n-1)\right]=\frac{n^{2}-2 n+2}{2}\] dominos in the longest proper sequence in $D_{n}.$ This bound is in fact attained for every even $n.$ It is easy to verify this for $n=2$, so assume inductively that a sequence of this length has been found for a particular value of $n$.


Without loss of generality, assume $i=1$ and $j=2,$ and let $_{p} X_{p+2}$ denote a four-domino sequence of the form $(p, n+1)(n+1, p+1)(p+1, n+2)(n+2, p+2) .$ By appending \[{ }_{2} X_{4},{ }_{4} X_{6}, \ldots,{ }_{n-2} X_{n},(n, n+1)(n+1,1)(1, n+2)(n+2,2)\] to the given proper sequence, a proper sequence of length \[\frac{n^{2}-2 n+2}{2}+4 \cdot \frac{n-2}{2}+4=\frac{n^{2}+2 n+2}{2}=\frac{(n+2)^{2}-2(n+2)+2}{2}\] is obtained that starts at $i=1$ and ends at $j=2 .$ This completes the inductive proof.


In particular, the longest proper sequence when $n=40$ is 761.

~phoenixfire

Note 2

In the language of graph theory, this is an example of an Eulerian circuit.

~phoenixfire

Solution 4

Consider the segments joining the vertices of a regular $n$-gon. For odd $n$, we see that the number of segments is quite easily $\binom{n-1}{2}$. This is because every vertex touches every other vertex the same number of times. ($\frac{n-1}{2}$ times to be exact). Hence the answer for odd cases is $n\frac{n-1}{2}=\binom{n-1}{2}$. (This is because a segment that starts at the first vertex also ends at the first vertex). For even $n$ however, every vertex touches $\frac{n-2}{2}$ vertices. However, one may be motivated to say that the answer (as in the odd case) is $n\frac{n-2}{2}$. But this is incorrect, because for the even case, it never ends at the vertex (the first vertex) you started at. So it must end at another vertex. But that vertex has already $\frac{n-2}{2}$ other segments touching it. So we have that the final answer is $1$ plus $n\frac{n-2}{2}$. The case for $n=40$, is $761$.

~th1nq3r

Note

The reason it touches every single other vertex $\frac{n-1}{2}$ for odd $n$ is because there are a total of $\binom{n-1}{2}$ segments, and once dividing $\binom{n-1}{2}$ by $n$, you will then have the number of segments that are connected to each vertex. For the even case every vertex has at least $\frac{n-2}{2}$ other segments touching it. This is because (you CAN convince yourself through a painful induction/observation argument, but you probably shouldn't) $n$ is even, and if you try to apply the odd case to the even case, (namely that there is $\frac{n-1}{2}$ segments touching each vertex), there would have to then be $n\frac{n-1}{2}$ total segments, which never works since it never loops back to the vertex you started on). So at LEAST, there should be $\frac{n-2}{2}$ segments touching each vertex. However, there is also at most $\frac{n-2}{2}$ segments touching each vertex. Hence by the (what I call) the "less-than-or-greater-than" argument, there must be $\frac{n-2}{2}$ segments out of each vertex. (Mind the plus one extra vertex since once again, the vertex you started on, it doesn't loop around, so it must end at another vertex). Hence the answer is $n\frac{n-2}{2}+1$.

(I am not very good at explaining things. Sorry if it didn't make sense. Maybe if you find some way to contact me on aops, I could try and help). (For instance, I could see possible confusion at the part where I claim that the minimum lines be $\frac{n-2}{2}$. You might think, "Oh why not $\frac{n-1}{2}-1$, or even $\frac{n-1}{2}-2$ or even subtract $3$?" Well if you actually start off with the fact that there should be at MOST $\frac{n-2}{2}$ segments from each vertex, then it is obvious, since then there must be a minimum of $\frac{n-2}{2}$ segments from each vertex).

~th1nq3r

Solution 5

We can see that $|D_{40}| = 780$, since we are choosing 2 integers $[1,40]$, and order doesn't matter because $(i,j)$ and $(j,i)$ aren't both in the set. Then from doing a smaller example of $D_4$, we can note that non-endpoints must have an even number of pairs in $D$ in order for one domino's end to match another's beginning. Then, in order to maximize the length we want to minimize the number of dominoes we remove to make all pairs be even (except endpoints). Then we can see that for every two pairs with an odd number of pairs, we can connect single ends to form a circular chain (i.e. if we want to ensure that 2,3 have even pairs then we can imagine (3,1)(1,2)). Thus we can divide 40 by 4 to get the number of numbers to remove. Thus we need to remove 10 numbers. But each number is connected to another, so we remove 20 dominoes. Thus there are 780-20 = 760 dominoes not including endpoints. Finally, we can add one more domino at the end since it doesn't need to match up with the first of another to make it 761.

See also

1998 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Last question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=1998_AIME_Problems/Problem_15&oldid=220847"