{"id":419,"date":"2009-04-23T07:26:31","date_gmt":"2009-04-23T06:26:31","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=419"},"modified":"2009-06-30T16:07:12","modified_gmt":"2009-06-30T14:07:12","slug":"najmniej-druzyn","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2009\/04\/23\/najmniej-druzyn\/","title":{"rendered":"Najmniej dru\u017cyn"},"content":{"rendered":"

Dzi\u0119kuj\u0119 Jazzowi, pixlowi i Micha\u0142owi, tak\u017ce\u00a0w imieniu mojego niepo\u0142amanego o\u0142\u00f3wka, za eleganckie dowody, \u017ce:<\/p>\n

nie ma takich pi\u0119ciu liczb naturalnych (bez zera) niepodzielnych przez 3 i 7, by suma ka\u017cdych dw\u00f3ch z nich by\u0142a podzielna przez 3 lub 7<\/em>.<\/p>\n

Na wyr\u00f3\u017cnienie zas\u0142uguje moim zdaniem dow\u00f3d pixla\u00a0– oparty na grafie i niemal klasyczny, bo bliski twierdzeniu i\u00a0liczbom Ramseya. Pixl wykaza\u0142, \u017ce \u017caden graf pe\u0142ny K5<\/sub><\/span> (5 wierzcho\u0142k\u00f3w) bez klik monochromatycznych K3<\/sub><\/span> nie spe\u0142nia warunk\u00f3w zadania („klika” to matematyczne okre\u015blenie podgrafu pe\u0142nego, a wi\u0119c\u00a0stanowi\u0105cego cz\u0119\u015b\u0107 wi\u0119kszego grafu pe\u0142nego).<\/p>\n

Dow\u00f3d mo\u017cna by upro\u015bci\u0107, nie koloruj\u0105c kraw\u0119dzi, a pozostaj\u0105c tylko przy liczbach lokowanych w wierzcho\u0142kach. Powinny one nale\u017ce\u0107 do dwu r\u00f3\u017cnych podzbior\u00f3w\u00a0– A i B (od tego zacz\u0119li Jazz i Micha\u0142), przy czym w wierzcho\u0142kach \u017cadnego tr\u00f3jk\u0105ta-kliki nie mog\u0105 wyst\u0119powa\u0107 liczby z tego samego podzbioru. S\u0105 zatem tylko dwa podstawowe sposoby umieszczenia liczb z podzbior\u00f3w A i B w wierzcho\u0142kach jakiego\u015b tr\u00f3jk\u0105ta, powiedzmy ostrok\u0105tnego:<\/p>\n

\"\"<\/a><\/p>\n

W obu przypadkach nie da si\u0119 oznaczy\u0107 dw\u00f3ch pozosta\u0142ych wierzcho\u0142k\u00f3w literami A i B tak, by nie pojawi\u0142 si\u0119 tr\u00f3jk\u0105t „monoliterowy”, czyli dochodzimy do sprzeczno\u015bci.<\/p>\n

Korzystanie z graf\u00f3w cz\u0119sto bywa pomocne przy dowodzeniu, ilustrowaniu lub rozwi\u0105zywaniu zada\u0144, w kt\u00f3rych wyst\u0119puj\u0105 zale\u017cno\u015bci mi\u0119dzy podzbiorami, zw\u0142aszcza gdy sformu\u0142owanie tych zale\u017cno\u015bci powoduje lekki m\u0119tlik w g\u0142owie\u00a0– jak w pami\u0119tnej \u0142amig\u0142\u00f3wce o dyngusowym polewaniu (dotychczas w komentarzach\u00a0pod wpisem „Dziewki i parobcy” nie pojawi\u0142o si\u0119 poprawne rozwi\u0105zanie; pomijaj\u0105c 1 parobka i 6 dziewek).<\/p>\n

Oto inny przyk\u0142ad, \u0142atwiejszy od „folwarcznego” zadania.<\/p>\n

Zako\u0144czy\u0142 si\u0119 turniej siatk\u00f3wki, w kt\u00f3rym ka\u017cde dwie dru\u017cyny rozegra\u0142y dok\u0142adnie jeden mecz<\/em>.<\/p>\n

Czyli na razie\u00a0sprawa jest jasna, nic trudnego do zrozumienia –\u00a0typowy system rozgrywek „ka\u017cdy z ka\u017cdym”, zwany tak\u017ce ko\u0142owym.\u00a0I oto\u00a0pojawia si\u0119 stwierdzenie wprowadzaj\u0105ce niejaki zam\u0119t:<\/p>\n

Dla dowolnych trzech dru\u017cyn mo\u017cna wskaza\u0107 tak\u0105, kt\u00f3ra pokona\u0142a ka\u017cd\u0105 z tych trzech<\/em>.<\/p>\n

I pytanie:<\/p>\n

Ile\u00a0dru\u017cyn startowa\u0142o w turnieju, je\u017celi liczba ta by\u0142a najmniejsz\u0105, przy kt\u00f3rej mog\u0142o pojawi\u0107 si\u0119 to zadanie?<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Dzi\u0119kuj\u0119 Jazzowi, pixlowi i Micha\u0142owi, tak\u017ce\u00a0w imieniu mojego niepo\u0142amanego o\u0142\u00f3wka, za eleganckie dowody, \u017ce: nie ma takich pi\u0119ciu liczb naturalnych (bez zera) niepodzielnych przez 3 i 7, by suma ka\u017cdych dw\u00f3ch z nich by\u0142a podzielna przez 3 lub 7. Na wyr\u00f3\u017cnienie zas\u0142uguje moim zdaniem dow\u00f3d pixla\u00a0– oparty na grafie i niemal klasyczny, bo bliski twierdzeniu […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/419"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=419"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/419\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}