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 "2009 Indonesia MO Problems/Problem 4"

(→‎Solution)
(→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 28: Line 28:
 
<math>F</math> has a degree of 3 or more. If <math>F</math> is connected to at least 2 elements from set <math>S</math>, then <math>A</math>, <math>F</math>, and these 2 vertices will form a loop with 4 elements. For example, if <math>F</math> is connected to <math>B</math> and <math>C</math>, then <math>A-B-F-C-A</math> will form a loop.
 
<math>F</math> has a degree of 3 or more. If <math>F</math> is connected to at least 2 elements from set <math>S</math>, then <math>A</math>, <math>F</math>, and these 2 vertices will form a loop with 4 elements. For example, if <math>F</math> is connected to <math>B</math> and <math>C</math>, then <math>A-B-F-C-A</math> will form a loop.
  
−
The only way for <math>F</math> to connect to 3 other vertices is by having an edge between <math>FG</math>, an edge between <math>AF</math>, and an edge between <math>F</math> and one of the vertices from set <math>S</math>. WLOG, let <math>FB</math> be the edge.
+
The only way for <math>F</math> to connect to 3 other vertices without forming a 4-vertices loop is by having an edge between <math>FG</math>, an edge between <math>AF</math>, and an edge between <math>F</math> and one of the vertices from set <math>S</math>. WLOG, let <math>FB</math> be the edge.
  
 
<asy>
 
<asy>
Line 55: Line 55:
 
</asy>
 
</asy>
  
−
Similar to <math>F</math>, <math>G</math> also connects to 3 other vertices. If <math>G</math> connects to 2 vertices from <math>S</math>, then <math>A</math>, <math>G</math>, and the 2 vertices will again form a 4 way loop. However, if <math>G</math> forms and edge with <math>A</math>, <math>A-B-F-G-A</math> will again be a 4-way loop. Thus, it's impossible to have <math>G</math> form an edge with 2 other vertices without creating a 4-way loop.
+
Similar to <math>F</math>, <math>G</math> also connects to 3 other vertices. If <math>G</math> connects to 2 vertices from <math>S</math>, then <math>A</math>, <math>G</math>, and the 2 vertices will again form a 4-vertices loop. However, if <math>G</math> forms an edge with <math>A</math>, <math>A-B-F-G-A</math> will again be a 4-vertices loop. Thus, it's impossible to have <math>G</math> form an edge with 2 other vertices without creating a 4-vertices loop.

Latest revision as of 12:37, 18 September 2024

Solution

Suppose that among the 7 vertices, each has a degree of 3. Then the total amount of edges will be $\frac{7\cdot 3}{2}$, which isn't an integer. Therefore, at least one vertex has a minimal degree of 4.

WLOG, let $A$ be the vertex with a degree of 4 or more. $A$ must be connected to at least 4 other vertices, name them $B$, $C$, $D$, and $E$, and name the set that contains these 4 vertices $S$.

[asy] pair A=(0,90),B=(120,180),C=(120,120),D=(120,60),E=(120,0); pair F=(240,120),G=(240,60); draw(B--A--C); draw(D--A--E); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); label("$A$",A,W); label("$B$",B,NW); label("$C$",C,NW); label("$D$",D,SW); label("$E$",E,SW); label("$F$",F,W); label("$G$",G,W); [/asy]

$F$ has a degree of 3 or more. If $F$ is connected to at least 2 elements from set $S$, then $A$, $F$, and these 2 vertices will form a loop with 4 elements. For example, if $F$ is connected to $B$ and $C$, then $A-B-F-C-A$ will form a loop.

The only way for $F$ to connect to 3 other vertices without forming a 4-vertices loop is by having an edge between $FG$, an edge between $AF$, and an edge between $F$ and one of the vertices from set $S$. WLOG, let $FB$ be the edge.

[asy] pair A=(0,90),B=(120,180),C=(120,120),D=(120,60),E=(120,0); pair F=(240,120),G=(240,60); draw(B--A--C); draw(D--A--E); draw(B--F--G); real f(real x) { return -x^2/100+2.525x+90; }; path pft = graph(f, 0, 240); draw(pft); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); label("$A$",A,W); label("$B$",B,NW); label("$C$",C,NW); label("$D$",D,SW); label("$E$",E,SW); label("$F$",F,W); label("$G$",G,W); [/asy]

Similar to $F$, $G$ also connects to 3 other vertices. If $G$ connects to 2 vertices from $S$, then $A$, $G$, and the 2 vertices will again form a 4-vertices loop. However, if $G$ forms an edge with $A$, $A-B-F-G-A$ will again be a 4-vertices loop. Thus, it's impossible to have $G$ form an edge with 2 other vertices without creating a 4-vertices loop.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_Indonesia_MO_Problems/Problem_4&oldid=227494"