Difference between revisions of "2009 Indonesia MO Problems/Problem 4"
Victorzwkao (talk | contribs) (Created page with "==Solution== Suppose that among the 7 vertices, each has a degree of 3. Then the total amount of edges will be <math>\frac{7\cdot 3}{2}</math>, which isn't an integer. Theref...") |
Victorzwkao (talk | contribs) (→Solution) |
||
| Line 26: | Line 26: | ||
</asy> | </asy> | ||
| − | <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>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 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. | ||
Revision as of 10:17, 18 September 2024
Solution
Suppose that among the 7 vertices, each has a degree of 3. Then the total amount of edges will be 
, which isn't an integer. Therefore, at least one vertex has a minimal degree of 4.
WLOG, let 
be the vertex with a degree of 4 or more. must be connected to at least 4 other vertices, name them 
, 
, 
, and 
, and name the set that contains these 4 vertices 
.
![[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]](http://latex.artofproblemsolving.com/9/c/9/9c94e4dc9e9737eb24d98400740772f7ea272477.png)
has a degree of 3 or more. If is connected to at least 2 elements from set , then , , and these 2 vertices will form a loop with 4 elements. For example, if is connected to and , then 
will form a loop.
The only way for to connect to 3 other vertices is by having an edge between 
, an edge between 
, and an edge between and one of the vertices from set . WLOG, let 
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]](http://latex.artofproblemsolving.com/6/f/8/6f8f24f0fb1fb00cadb77707be82db58b86c6cb3.png)
Similar to , 
also connects to 3 other vertices. If connects to 2 vertices from , then , , and the 2 vertices will again form a 4 way loop. However, if forms and edge with , 
will again be a 4-way loop. Thus, it's impossible to have form an edge with 2 other vertices without creating a 4-way loop.
