{"id":423,"date":"2009-04-26T07:59:46","date_gmt":"2009-04-26T06:59:46","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=423"},"modified":"2009-04-26T07:59:46","modified_gmt":"2009-04-26T06:59:46","slug":"jak-to-sie-robi","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2009\/04\/26\/jak-to-sie-robi\/","title":{"rendered":"Jak to si\u0119 robi…"},"content":{"rendered":"

Nikt nie poradzi\u0142 sobie z siatkarskim zadaniem z poprzedniego wpisu, a przynajmniej nie pochwali\u0142 si\u0119 w komentarzu. Co prawda proste nie by\u0142o, ale nie przypuszcza\u0142em, \u017ce a\u017c tak. Jestem zaskoczony, bo liczba odwiedzaj\u0105cych \u0141amiblog jest, m\u00f3wi\u0105c ogl\u0119dnie, niema\u0142a, cho\u0107 komentator\u00f3w\u00a0– jak to zwykle bywa\u00a0– znacznie skromniejsza. By\u0107 mo\u017ce pogoda nie sprzyja g\u0142\u00f3wkowaniu, a mo\u017ce wszyscy, zw\u0142aszcza maturzy\u015bci, kuj\u0105 do egzamin\u00f3w. Jakkolwiek by nie by\u0142o, postanowi\u0142em\u00a0– jak m\u00f3wi znajomy nauczyciel\u00a0– „odwali\u0107 kawa\u0142ek dobrej (mam nadziej\u0119), nikomu niepotrzebnej (mam nadziej\u0119, \u017ce nie) roboty edukacyjnej”. Opisz\u0119 mianowicie, w ramach podpowiedzi, jak radzi\u0142bym sobie z prostszym o jeden szczebel wariantem tej \u0142amig\u0142\u00f3wki. Zaczn\u0119 od przypomnienia zadania w og\u00f3lnej formie.<\/p>\n

W turnieju siatk\u00f3wki startowa\u0142o n<\/strong> dru\u017cyn. Ka\u017cda rozegra\u0142a jeden mecz z ka\u017cd\u0105 z pozosta\u0142ych. Dla ka\u017cdych m<\/strong> dru\u017cyn (oczywi\u015bcie m<\/strong> < n<\/strong>) mo\u017cna w\u015br\u00f3d pozosta\u0142ych wskaza\u0107 tak\u0105, kt\u00f3ra pokona\u0142a ka\u017cd\u0105 z tych m<\/strong>. Prosz\u0119 znale\u017a\u0107 najmniejsze mo\u017cliwe n<\/strong><\/em>.<\/p>\n

Dla m<\/strong><\/em> = 1 przypadek jest trywialny. Ka\u017cda dru\u017cyna przegrywa i wygrywa jeden mecz, czyli w turnieju uczestnicz\u0105 trzy.<\/p>\n

Dla m<\/strong><\/em> = 2 zadanie si\u0119 komplikuje i to od razu do\u015b\u0107 mocno.
\nKa\u017cda dru\u017cyna uleg\u0142a x<\/strong><\/em> zespo\u0142om i pokona\u0142a y<\/strong><\/em>. Rozwa\u017cmy sytuacj\u0119 dru\u017cyny A<\/strong><\/em> pokonanej przez nale\u017c\u0105cy do x<\/em><\/strong> zesp\u00f3\u0142 B<\/strong><\/em>, czyli:<\/p>\n

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

B<\/strong><\/em> powinna przegra\u0107 przynajmniej z jedn\u0105 z pozosta\u0142ych x<\/strong><\/em>, bo inaczej para A<\/em><\/strong>–B<\/strong><\/em> nie mia\u0142aby swojego pogromcy. Uog\u00f3lniaj\u0105c, ka\u017cda z dru\u017cyn x<\/strong><\/em> musia\u0142a dozna\u0107 przynajmniej jednej pora\u017cki z inn\u0105 dru\u017cyn\u0105 z x<\/em><\/strong>, a st\u0105d wniosek, \u017ce x<\/strong><\/em>\u00a0jest nie mniejsze ni\u017c<\/span>\u00a03 (tu k\u0142ania si\u0119 wariant dla m<\/em><\/strong> = 1).
\nZ drugiej strony w\u015br\u00f3d wszystkich zespo\u0142\u00f3w musi by\u0107 cho\u0107 jedna taka dru\u017cyna A<\/strong><\/em>, kt\u00f3ra wygra\u0142a co najmniej tyle mecz\u00f3w, co przegra\u0142a (w przeciwnym wypadku og\u00f3lna liczna zwyci\u0119stw by\u0142aby mniejsza od og\u00f3lnej liczby pora\u017cek). Ta dru\u017cyna dozna przynajmniej trzech pora\u017cek z zespo\u0142ami z x<\/em><\/strong> oraz pokona nie mniej ni\u017c trzy dru\u017cyny z y<\/strong><\/em>, a to mo\u017cliwe jest tylko w\u00f3wczas, gdy wszystkich dru\u017cyn b\u0119dzie co najmniej 7. Proste?<\/p>\n

Dowodem, \u017ce to mo\u017cliwe, jest poni\u017cszy graf turnieju z udzia\u0142em 7 dru\u017cyn. Ka\u017cda para wierzcho\u0142k\u00f3w jest „osaczona” przez dwie strza\u0142ki-pora\u017cki wychodz\u0105ce z trzeciego wierzcho\u0142ka.<\/p>\n

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

A teraz prosz\u0119 spr\u00f3bowa\u0107 samemu upora\u0107 si\u0119 z wariantem dla m<\/strong><\/em> = 3.<\/p>\n","protected":false},"excerpt":{"rendered":"

Nikt nie poradzi\u0142 sobie z siatkarskim zadaniem z poprzedniego wpisu, a przynajmniej nie pochwali\u0142 si\u0119 w komentarzu. Co prawda proste nie by\u0142o, ale nie przypuszcza\u0142em, \u017ce a\u017c tak. Jestem zaskoczony, bo liczba odwiedzaj\u0105cych \u0141amiblog jest, m\u00f3wi\u0105c ogl\u0119dnie, niema\u0142a, cho\u0107 komentator\u00f3w\u00a0– jak to zwykle bywa\u00a0– znacznie skromniejsza. By\u0107 mo\u017ce pogoda nie sprzyja g\u0142\u00f3wkowaniu, a mo\u017ce wszyscy, […]<\/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\/423"}],"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=423"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/423\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=423"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=423"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=423"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}