{"id":517,"date":"2009-08-07T08:19:23","date_gmt":"2009-08-07T06:19:23","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=517"},"modified":"2009-10-06T09:10:44","modified_gmt":"2009-10-06T07:10:44","slug":"winogrona","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2009\/08\/07\/winogrona\/","title":{"rendered":"Winogrona"},"content":{"rendered":"

Wyobra\u017cam sobie, \u017ce Ci z Pa\u0144stwa, kt\u00f3rzy nadsy\u0142aj\u0105 rozwi\u0105zania zada\u0144, stanowi\u0105\u00a0grup\u0119 nieoficjalnych przedstawicieli licznego grona rozwi\u0105zuj\u0105cych, oddelegowan\u0105 do o\u017cywiania \u0141amibloga, czyli ku pokrzepieniu serca autora. Wielkie dzi\u0119ki dla wszystkich „chwal\u0105cych si\u0119” rozwi\u0105zaniami. Ciesz\u0105 tak\u017ce do\u0142\u0105czane do rozwi\u0105za\u0144 komentarze – wszystkie, ale zw\u0142aszcza te sk\u0142aniaj\u0105ce do refleksji lub do rozwini\u0119cia tematu.
\nMicha\u0142 napisa\u0142, \u017ce zadanie z poprzedniego wpisu nie podoba\u0142o si\u0119, bo ma\u0142o w nim do my\u015blenia, g\u0142\u00f3wnie „guess-and-check”<\/em>. Polemizowa\u0142bym, \u017ce jednak nie tak ma\u0142o, a nawet przynajmniej p\u00f3\u0142 na p\u00f3\u0142, je\u015bli nie zabiera\u0107 si\u0119 zbyt szybko\u00a0za pr\u00f3bowanie i b\u0142\u0105dzenie, kt\u00f3re wcze\u015bniej mo\u017cna elegancko ograniczy\u0107 i zaplanowa\u0107. Wystarczy zauwa\u017cy\u0107, \u017ce do wpisania zosta\u0142o sze\u015b\u0107 liczb nieparzystych (N) i sze\u015b\u0107 parzystych (P), a to pozwala ustali\u0107 tylko trzy mo\u017cliwe schematy rozmieszczenia liczb:<\/p>\n

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

W pierwszym i drugim trzeci rz\u0105d jest taki sam, wi\u0119c oba mo\u017cna sprawdza\u0107 w tym samym „podej\u015bciu” i do\u015b\u0107 szybko wyeliminowa\u0107. Pozostaje kr\u00f3tkie b\u0142\u0105dzenie w trzecim schemacie; warto przy tym pami\u0119ta\u0107, \u017ce liczba 15 musi znale\u017a\u0107 si\u0119\u00a0w podstawie tr\u00f3jk\u0105ta.
\nRozwi\u0105zanie jest jedno, a zatem w tr\u00f3jk\u0105cie r\u00f3\u017cnicowym pi\u0105tego rz\u0119du (5-liczbowy bok), czyli utworzonym z liczb od 1 do n<\/em> = 15, rozmieszczenie liczb jest unikatowe (z dok\u0142adno\u015bci\u0105 do symetrii). Dla \u017cadnego n<\/em> > 15 takiego tr\u00f3jk\u0105ta nie spos\u00f3b utworzy\u0107, cho\u0107 nie\u0142atwo tego dowie\u015b\u0107. Dla n<\/em> = 21 mo\u017cna to zrobi\u0107 w „toporny” spos\u00f3b, rozpisuj\u0105c wszystkie og\u00f3lne schematy N-P (analogiczne jak ka\u017cdy\u00a0 z trzech powy\u017cej); potem wystarczy zauwa\u017cy\u0107, \u017ce \u017caden z nich nie sk\u0142ada si\u0119 z jedenastu N i dziesi\u0119ciu P.
\nJest jednak znany bardziej og\u00f3lny i elegancki dow\u00f3d niemo\u017cno\u015bci utworzenia tr\u00f3jk\u0105t\u00f3w r\u00f3\u017cnicowych rz\u0119du 2^k<\/em>\u00a0– 2 (k > 1). Polega on na wykazaniu, \u017ce suma liczb w takim tr\u00f3jk\u0105cie powinna by\u0107 parzysta, co prowadzi do sprzeczno\u015bci, bo dla rz\u0119d\u00f3w okre\u015blonych podanym wzorem warto\u015bci n<\/em> s\u0105 nieparzyste (3, 21, 105, 465, 1953, 8001…), a wi\u0119c suma liczb od 1 do\u00a0n<\/em> tak\u017ce\u00a0musi by\u0107\u00a0nieparzysta. Istnieje\u00a0wreszcie bardzo pomys\u0142owy, ale trudny dow\u00f3d, \u017ce tr\u00f3jk\u0105ty r\u00f3\u017cnicowe rz\u0119du nie mniejszego ni\u017c\u00a09 w og\u00f3le nie mog\u0105 istnie\u0107. Dla rz\u0119d\u00f3w 6, 7 i 8\u00a0ten dow\u00f3d si\u0119 nie sprawdza, ale trzy krn\u0105brne przypadki nietrudno wykluczy\u0107, pisz\u0105c odpowiedni program na komputer (nie wspominaj\u0105c o podanych wy\u017cej sposobach dla sz\u00f3stego rz\u0119du).<\/p>\n

Je\u017celi z liczb od 1 do 21 usun\u0105\u0107 jak\u0105\u015b nieparzyst\u0105 (ale nie dowoln\u0105), zast\u0119puj\u0105c j\u0105 kolejn\u0105 liczb\u0105, czyli 22, to w\u00f3wczas utworzenie tr\u00f3jk\u0105ta r\u00f3\u017cnicowego b\u0119dzie mo\u017cliwe,\u00a0jednak to \u0142amig\u0142\u00f3wka i\u015bcie benedykty\u0144ska, niemal wy\u0142\u0105cznie guess-and-check<\/em>. Zdziwi\u0142em si\u0119, znajduj\u0105c takie zadanie (z usuni\u0119t\u0105 pi\u0119tnastk\u0105) w szkolnym konkursie<\/a>. Je\u015bli kto\u015b zna metod\u0119\u00a0rozgryzienia tego orzecha\u00a0na logik\u0119, wdzi\u0119czny b\u0119d\u0119 za informacj\u0119.<\/p>\n

\u0141amig\u0142\u00f3wki bliskie\u00a0tr\u00f3jk\u0105tom r\u00f3\u017cnicowym, ale\u00a0zw\u0142aszcza tr\u00f3jk\u0105towi Pascala, by\u0142y przed laty w modzie. Pojawi\u0142y si\u0119\u00a0mi\u0119dzy innymi\u00a0jako Winogrona<\/em> na \u0141amig\u0142\u00f3wkowych Mistrzostwach \u015awiata w Brnie w 2001 roku. Zapraszam do posmakowania lekkostrawnych\u00a0„owoc\u00f3w” z Mistrzostw,\u00a0lecz\u00a0w formie\u00a0indugadki, czyli regu\u0142y zabawy\u00a0nale\u017cy samemu wyindukowa\u0107\u00a0na podstawie przyk\u0142adu\u00a0 z rozwi\u0105zaniem.<\/p>\n

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

Nietrudno zauwa\u017cy\u0107, co wsp\u00f3lnego maj\u0105 Winogrona<\/em> z tr\u00f3jk\u0105tem r\u00f3\u017cnicowym. Wystarczy obr\u00f3ci\u0107 ki\u015b\u0107 z przyk\u0142adowym rozwi\u0105zaniem o 60 stopni zgodnie z ruchem wskaz\u00f3wek zegara.<\/p>\n","protected":false},"excerpt":{"rendered":"

Wyobra\u017cam sobie, \u017ce Ci z Pa\u0144stwa, kt\u00f3rzy nadsy\u0142aj\u0105 rozwi\u0105zania zada\u0144, stanowi\u0105\u00a0grup\u0119 nieoficjalnych przedstawicieli licznego grona rozwi\u0105zuj\u0105cych, oddelegowan\u0105 do o\u017cywiania \u0141amibloga, czyli ku pokrzepieniu serca autora. Wielkie dzi\u0119ki dla wszystkich „chwal\u0105cych si\u0119” rozwi\u0105zaniami. Ciesz\u0105 tak\u017ce do\u0142\u0105czane do rozwi\u0105za\u0144 komentarze – wszystkie, ale zw\u0142aszcza te sk\u0142aniaj\u0105ce do refleksji lub do rozwini\u0119cia tematu. Micha\u0142 napisa\u0142, \u017ce zadanie z […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/517"}],"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=517"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/517\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}