Every pair of communities in a county are linked directly by one mode of transportation; bus, train, or airplane. All three methods of transportation are used in the county with no community being serviced by all three modes and no three communities being linked pairwise by the same mode. Determine the largest number of communities in this county.
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, combinatorics unsolved, combinatorics, Hi
27.07.2011 12:11
29.08.2023 19:36
This is just saying the maximum number of vertices in a 3-colored graph that uses all colors, has no monochromatic triangle, and no vertex uses all three colors. Call the colors red, green, and blue. We claim the answer is 4. Make a red 4-cycle and the diagonals one blue and one green for the construction. The main idea of the problem is the following claim: Claim: A vertex cannot have 3 or more edges of the same color going out of it. Suppose otherwise. Then, there exist four vertices $A,B,C,D$ such that the edges $AB,AC,AD$ are all the same color, say red. Now, the triangle $\triangle BCD$ must only have green and blue, since any red edge would cause a monochromatic triangle with vertex A. However, since $\triangle BCD$ also cannot be a monochromatic triangle, there must be at least one green edge and one blue edge. However, the common vertex of these two edges will have a green edge and a blue edge, but it will also have a red edge to $A$, contradiction, hence shown. This claim immediately rules out $n\geq6$ by pidgeonhole. For $n=5$, this claim also tells us that each vertex must have 2 edges of some color, 2 of another, and none of the last color. For now, consider the subgraph formed on the same vertex set but with only the red edges. Each vertex must have degree 2 or 0, so it must be some union of cycles. Since monochromatic triangles are not allowed, the smallest possible is a 4-cycle, which has 4 edges. Hence, there are at least 4 red edges. Similarly, since all colors are used at least once, there are also at least 4 blue edges and at least 4 green edges, contradiction since there are only 10 edges total, hence done.
30.08.2023 18:55
03.01.2024 07:32
Consider a graph $K_n$ with edges colored $A$, $B$, or $C$. Define $A_i$, $B_i$, $C_i$ as the number of color $A$, $B$, $C$ edges incident on vertex $i$. Note that $A_i+B_i+C_i=n-1$ and $\min(A_i,B_i,C_i) = 0$. With the conditions in the problem, we can undercount the number of triangles in the graph as \begin{align*} \binom n3 &\ge \sum \binom{A_i}{2} + \binom{B_i}{2} + \binom{C_i}{2} \\ &\ge \sum 2 \cdot \binom{(n-1)/2}{2} \\ &= 2n \cdot \binom{(n-1)/2}{2} \\ &\implies n \leq 5. \end{align*} However the equality case $n=5$ holds if and only if each vertex has two edges each of two colors. This forces us to have at least 4 edges of each color, or 12 total, contradiction. We conclude our answer is $\boxed{4}$, which is easy to construct. $\blacksquare$
29.02.2024 05:06
The answer is $\boxed{n=4}$, which is easily constructible. The corresponding graph is $K_n$ with each edge colored one of three colors, say red, blue, and green. The conditions then become that no vertex can have three distinct colors emanating from it, and there are no monochromatic triangles in the graph. If $n \ge 6$, there are $5$ edges for each vertex. This requires at least three of them to be the same color. WLOG let that color be red. Assume that vertex is $A$, and the edges are $AB$, $AC$, and $AD$. In triangle $BCD$, none of them can be red, so they must be only blue or green. By Pigeonhole, there is a point that has a blue and a green edge emanating from it, hence this is a contradiction, since it is also connected to red. For $n=5$, each vertex has $2$ edges of a certain color. Hence, we can consider the subgraph formed by the red edges. It is clear that the minimum degree of a cycle is $4$, which means there are at least $4$ edges of each color, a contradiction as there are only $10$ edges in the graph. Thus, $n \le 4$, which proves the bound.
10.08.2024 03:33
The answer to $n=4$. A construction for $n=4$ is to make a square with its sides all one mode of transportation, and the diagonals each a different mode of transportation from the sides and other diagonal. It remains to show $n \geq 5$ is impossible, and it suffices to show $n=5$ is impossible (since we are working with complete graphs). This problem admits certain not-so-elegant brute force solutions. The key to a more elegant solution is to partition the communities into three groups. Let group $X$ contain communities that allow only bus and train. Let group $Y$ contain communities that allow only train and airplane. Let group $Z$ contain communities that allow only bus and airplane. If a town only allows one mode of transportation, it can be put in any of the two groups that allow that mode. In this partition, at least two of the groups must be non-empty, based on the condition that all three modes of transportation are used at least once. Suppose exactly two of the groups are non-empty, and WLOG let them be groups $X$ and $Y$. We claim that neither group can have more than two communities. For contradiction, assume WLOG that group $X$ has any three communities $x_1, x_2, x_3$, and that $y$ is any community in group $Y$. Then, the link between $x_i$ and $y$ for each $i$ must be by train. This means that in order to not form triangles of the same mode, the link between $x_i$ and $x_j$ for $i \neq j$ must be by bus. However, this means that we have created a triangle anyway. Thus, when exactly two of the groups are non-empty, the maximum number of communities is $2 \cdot 2 = 4$. Next, suppose that all three groups are non-empty. We claim that each group can only have one community. Suppose for contradiction that a group, WLOG $X$, has any two communities $x_1$ and $x_2$, and let $y$ and $z$ be communities from their respective groups. Then, $x_1y$ and $x_2y$ are connected by train, $yz$ is connected by airplane, and $x_1z$ and $x_2z$ are connected by bus. Now, no matter what, the connection of $x_1x_2$ will produce a contradiction. Thus, in this case, we cannot have more than $3$ communities, concluding the proof.
11.08.2024 12:57
rephrase to non stupid language. answer is 4, construct a square, top side connected by blue, bottom by green, rest by red. now label each vertex with the colors it's connected too. we pretend all vertices have 2 colors, if they don't then the graph disconnects or the arguments in the next section still hold true. take two RB vertices. if these exists a BG vertex, then it forms a blue bi angle , if there is an RG vertex there is one for red, so edge between the two RB vertices cannot be either, impossible now this implies for n>3 we cannot have all three pairs of labels (RB, RG, BG), and we also must at least have two since all modes of transport appear, so consider us having x RB and y RG, clearly everything from the RB to RG is red, so nothing between RBs and RGs can be red, forcing x,y <=2 as desired
04.10.2024 21:29
Let n be the number of communities. Let a, b and c be the colors of the edges. If $n \geq 6$, we have 3 edges from the same color coming from a vertex. Now WLOG, let them be colored in color b. Now one of the edges connecting one of the b-b pairs should be in color a for example. Now from that vertex we can only have edges with a and b. Since this vertex is in an edge connecting b-b again, this edge should be colored in a, but now there is an edge coming from a vertex already having edges from color a and b, that should be in color a or b and it is in both triangle with a-a edges and b-b edges $\Rightarrow$ we get a monochromatic triangle here - contradiction. Now for n = 5, each vertex has 2 edges of a certain color $\Rightarrow$ there are at least 4 edges of each color - contradiction since there are only 10 edges in the graph $\Rightarrow$ $n \leq 4$. It is only left to show that n = 4 works. The example is the $K_4$ where the graph looks like a square and the two bases and two diagonals are in color a, one of the other edges is in b and the last on in c. This works $\Rightarrow$ n = 4 and we are ready.