« Gammalt Handledningsforum (Gör ej nya inlägg)

Anonymous User

Kombinatorik IV Fråga 5

6 replies
Last
Hej, jag har kört fast på fråga 5 som lyder: "Varje kant i K_18 målas i en av två färger. Visa att det finns fyra hörn sådana att alla kanter mellan dessa fyra hörn är målade med samma färg. "


K_18 är alltså en komplett graf med 18 hörn. Jag har sett ledtråden om att använda exempel 15.13 samt lådprincipen men vet ändå inte hur de ska appliceras på uppgiften... Har kommit fram till att det är 153 kanter totalt i grafen och vi vet ju att vardera av de 18 hörnen har grad 17, men jag förstår ändå inte riktigt hur jag ska gå vidare. Mycket tacksam om någon har något tips :) 

18målas i en av två färger. Visa att det finns fyrahörn sådana att alla kanter mellan dessa fyra hörn är målade med sammafärg

6 replies
  1. Post by Joel Persson
    Re: Kombinatorik IV Fråga 5
    Hej!

    Här har du två tips:
    Resultatet (dvs. det som visades) från 15.13 kan vara väldigt användbart här, det är ju nästan en mindre variant av problemet.
    Vad kan du säga om hur många kanter av varje färg ett hörn har?
    Hoppas detta hjälper!

    MVH
    Joel Persson

    1 reply
  2. Parent of this post↑ Reply to JPJoel Persson from Anonymous User
    Re: Kombinatorik IV Fråga 5
    Hej, tack för svar! Förstår tyvärr inte alls 15.13, eller hur det kopplas till detta problem... Vi vet väl ingenting om hur många kanter som är i respektive färg, utifrån frågan tolkar jag det som att alla hade kunnat vara i en färg då vi inte vet något om fördelningen?
    1 reply
  3. Parent of this post↑ Reply to AUAnonymous User from Joel Persson
    Re: Kombinatorik IV Fråga 5
    Hej! Jag var ju inte jättetydlig i min kommentar så här kommer lite förtydligande:

    Alla kanter är ju antingen den ena eller den andra färgen så om ett hörn inte har några tillkopplade kanter av en färg måste den ha alla i den andra

    Säg att ett hörn har mindre än 3 färgade kanter av den ena färgen, då säger det något om den andra färgen. 

    Nyckeln här är att kantfallen (när som du sa exempelvis alla kanter har samma färg) är rätt lätta att visa. Börja med att fundera på om ifall du skulle kunna använda det som man kom fram till i exempel 15.13 i specialfallet där ett hörn hade alla kanter i en färg och se om du kan utvidga det generellt.
    Hoppas det hjälper!

    MVH
    Joel

  4. Post by Anonymous User
    Re: Kombinatorik IV Fråga 5
    Hej igen, tack för hjälpen! Jag vet inte om jag missuppfattar frågan. Jag tänker att det finns fall där påståendet inte stämmer? Exempelvis om ett hörn har att alla kanter är röda, då får resterande hörn också en röd kant, men resterande kanter kan ju vara ex blåa. Men eftersom alla har en kant som är röd finns ju inte 4 stycken hörn som har att alla kanter till dessa hörn är målade i samma färg då alla hörn har två färger på kanterna
    1 reply
  5. Parent of this post↑ Reply to AUAnonymous User from Joel Persson
    Re: Kombinatorik IV Fråga 5
    Hej! Det är kanterna mellan de fyra hörnen som det ska vara så om resterande kanter är blåa så behöver du ju bara ta 4 av de andra hörnen som då alla bara har blåa kanter mellan sig.

    MVH
    Joel

  6. Post by Anonymous User
    Re: Kombinatorik IV Fråga 5
    Okej tack, då förstår jag! Men i Exempel 15.13, varför tas just de två fallen upp i lösningen? Alltså varför kollar man på " 

    (1) det finns ett hörn v ur vilket utgår minst 6 blå kanter, och (2) det finns ett hörn med som mest fyra blå kanter."

Older discussion
Newer discussion