Hur många känner varandra i grupp av 6 personer - Dirichlets lådprincip
Hej!
Jag har en fråga angående en uppgift där man ska använda sig av Dirichlets lådprincip.
Uppgiften: Visa att man i varje grupp med sex personer antingen kan plocka ut tre personer som alla känner varandra eller tre personer där ingen av dem känner någon annan.
Jag kommer fram till ett någorlunda bevis när B,C och D känner A, E och F inte känner A. Men det blir problem när det endast är två som känner A och tre som inte känner A.
Min fråga är: Om B känner C men inte D, måste då E och F känna varandra? Jag vet inte hur jag ska kunna visa att E och F måste känna varandra.
Tack på förhand!
Det får finnas max 2 disjunkta vängrupper. Annars kan du alltid plocka ut 3 personer som inte känner varandra.
Tack. Vad betyder disjunkta vängrupper?
Jag missbrukade nog begreppet disjunkt. Men det jag menade var att det inte finns någon koppling mellan dem.
T.ex A-B, C-D, E-F fungera inte, det är 3 "disjunkta" vängrupper. Då kan du alltid plocka ut 3 personer som inte känner varandra.
Däremot kommer A-B-C-D, E-F fungera.
Tack så mycket!
Har jag förstått rätt nu:
Fall 1
B och C känner varandra men inte D -> ingen grupp kan tas ut
E och F känner varandra -> grupp kan tas ut
Fall 2
B och C känner varandra men inte D -> ingen grupp kan tas ut
E och F känner inte varandra -> ingen grupp kan tas ut
A, D och B känner inte varandra -> grupp kan tas ut
Jag gjorde en annan förklaring som kanske är lättare att följa:
Minst två av B,C och D känner inte varandra (2 eller 3 känner inte varandra) -> grupp kan skapas
Kvittar om E och F känner varandra
Två av B,C och D känner varandra men inte den tredje (B och C känner varandra men inte D)
Fall 1
E och F känner varandra -> grupp kan skapas
Fall 2
E och F känner inte varandra
Känner Känner inte
B-C E-F
A-E A-B
A-F A-C
A-D
B-D
C-D
Kan av listan “känner inte” välja ut A, C och D i en grupp där ingen känner någon annan
