Pagma-map ng mga koneksyon sa iyong susunod na shindig. unclibraries_commons 

Sabihin nating pinaplano mo ang iyong susunod na partido at naghihirap sa listahan ng bisita. Kanino ka dapat magpadala ng mga imbitasyon? Anong kumbinasyon ng mga kaibigan at estranghero ang tamang paghahalo?

Ito ay lumiliko out ang mga mathematicians ay nagtatrabaho sa isang bersyon ng problemang ito para sa halos isang siglo. Depende sa kung ano ang gusto mo, ang sagot ay maaaring kumplikado.

Ang aming aklat, "Ang Kamangha-manghang World of Graph Theory, "Sinisiyasat ang mga puzzle tulad ng mga ito at nagpapakita kung paano sila maaaring malutas sa pamamagitan ng mga graph. Maaaring mukhang maliit ang tanong na tulad nito, ngunit isang magandang pagpapakita kung paano magagamit ang mga graph upang malutas ang mga problema sa matematika sa mga magkakaibang larangan tulad ng mga siyensiya, komunikasyon at lipunan.

Ipinanganak ang palaisipan

Habang kilalang-kilala na ang Harvard ay isa sa mga nangungunang mga unibersidad sa bansa, maaari kang mabigla upang malaman na nagkaroon ng oras na ang Harvard ay isa sa mga pinakamahusay na koponan ng football sa bansa. Ngunit sa 1931, pinangunahan ng All-American quarterback na Barry Wood, ganito ang kaso.

Noong panahong iyon, naglaro si Harvard ng Army. Sa oras na iyon, hindi inaasahan, ang Army na humantong sa Harvard 13-0. Malinaw na napakasama, sinabi ng pangulo ng Harvard sa komandante ng mga kadete ng Army na habang ang Army ay maaaring mas mahusay kaysa sa Harvard sa football, ang Harvard ay higit na mataas sa mas kumpiskang kumpetisyon.

Bagaman bumalik si Harvard upang talunin ang Army 14-13, tinanggap ng komandante ang hamon upang makipagkumpetensya laban sa Harvard sa isang bagay na higit pang mga scholar. Sinang-ayunan na ang dalawa ay makikipagkumpetensya - sa matematika. Ito ang humantong sa Army at Harvard pagpili ng mga koponan sa matematika; ang pagbubunyag ay naganap sa West Point sa 1933. Sa pagkagulat ni Harvard, nanalo ang Army.

Ang kumpetisyon ng Harvard-Army sa kalaunan ay humantong sa isang taunang kumpetisyon sa matematika para sa mga undergraduates sa 1938, na tinatawag na Pagsusulit sa Putnam, pinangalanan para kay William Lowell Putnam, isang kamag-anak ng pangulo ng Harvard. Ang pagsusuring ito ay dinisenyo upang pasiglahin ang isang malusog na tunggalian sa matematika sa Estados Unidos at Canada. Sa paglipas ng mga taon at nagpapatuloy hanggang sa araw na ito, ang pagsusulit na ito ay naglalaman ng maraming mga kagiliw-giliw at madalas na mahirap na mga problema - kabilang ang isa na aming naglalarawan sa itaas.

Pula at asul na mga linya

Ang 1953 exam ay naglalaman ng mga sumusunod na problema (reworded ng kaunti): May anim na puntos sa eroplano. Ang bawat punto ay konektado sa bawat iba pang mga punto sa pamamagitan ng isang linya na alinman sa asul o pula. Ipakita na may tatlo sa mga puntong ito sa pagitan lamang ng mga linya ng parehong kulay ang iguguhit.

Sa matematika, kung mayroong isang koleksyon ng mga puntos na may mga linya na iguguhit sa pagitan ng ilang mga pares ng mga puntos, ang istraktura na iyon ay tinatawag na isang graph. Ang pag-aaral ng mga graph na ito ay tinatawag na graph theory. Gayunman, sa graph theory, ang mga punto ay tinatawag na vertices at ang mga linya ay tinatawag na mga gilid.

Ang mga graph ay maaaring gamitin upang kumatawan sa maraming uri ng mga sitwasyon. Halimbawa, sa problemang ito ng Putnam, ang isang punto ay maaaring kumatawan sa isang tao, ang isang pulang linya ay maaaring nangangahulugan na ang mga tao ay kaibigan at isang asul na linya ay nangangahulugan na sila ay mga estranghero.

Ipakita na mayroong tatlong punto na konektado sa pamamagitan ng mga linya ng parehong kulay. Gary Chartrand

Halimbawa, tawagan natin ang mga punto A, B, C, D, E, F at piliin ang isa sa mga ito, sabihin A. Sa limang linya na nakuha mula A hanggang sa iba pang limang punto, dapat mayroong tatlong linya ng parehong kulay.

Sabihin ang mga linya mula sa A hanggang B, C, D ay lahat pula. Kung ang isang linya sa pagitan ng alinman sa dalawang B, C, D ay pula, pagkatapos ay mayroong tatlong puntos na may mga pulang linya lamang sa pagitan nila. Kung walang linya sa pagitan ng alinman sa dalawang B, C, D ay pula, pagkatapos ay lahat ay asul.

Paano kung may limang puntos lamang? Maaaring walang tatlong puntos kung saan ang lahat ng mga linya sa pagitan ng mga ito ay may kulay na pareho. Halimbawa, ang mga linya na A-B, B-C, C-D, D-E, E-A ay maaaring pula, kasama ang iba pang asul.

Mula sa kung ano ang nakita natin, kung gayon, ang pinakamaliit na bilang ng mga tao na maaaring iimbitahan sa isang partido (kung saan ang bawat dalawang tao ay alinman sa mga kaibigan o mga estranghero) na may tatlong magkakaibigang kaibigan o tatlong magkakaibang estranghero ay anim.

Paano kung gusto namin ng apat na tao na magkasamang kaibigan o magkaibang estranghero? Ano ang pinakamaliit na bilang ng mga tao na dapat naming anyayahan sa isang partido upang tiyakin ito? Nasagot ang katanungang ito. Ito ay 18.

Paano kung nais namin ang limang tao na magkasamang kaibigan o magkakaibang estranghero? Sa sitwasyong ito, ang pinakamaliit na bilang ng mga tao na mag-anyaya sa isang partido na garantisadong ito ay - hindi kilala. Walang nakakaalam. Habang ang problemang ito ay madali upang ilarawan at marahil tunog sa halip simple, ito ay notoriously mahirap.

Ramsey numero

Ang aming tinatalakay ay isang uri ng numero sa teorya ng graph na tinatawag na Ramsey number. Ang mga numerong ito ay pinangalanan para sa British pilosopo, ekonomista at dalub-agbilang Frank Plumpton Ramsey.

Si Ramsey ay namatay sa edad na 26 ngunit nakuha sa kanyang napakaagang edad isang napaka-kakaiba teorama sa matematika, na nagbigay sa aming tanong dito. Sabihing mayroon kaming isa pang eroplano na puno ng mga puntos na konektado sa pamamagitan ng pula at asul na mga linya. Pumili kami ng dalawang positive integers, pinangalanan r at s. Gusto naming magkaroon ng eksaktong r puntos kung saan ang lahat ng mga linya sa pagitan ng mga ito ay pula o s puntos kung saan ang lahat ng mga linya sa pagitan ng mga ito ay asul. Ano ang pinakamaliit na bilang ng mga puntong maaari naming gawin ito? Iyon ay tinatawag na numero ng Ramsey.

Halimbawa, sabihin nating gusto natin ang aming eroplano na magkaroon ng hindi bababa sa tatlong punto na konektado ng lahat ng mga pulang linya at tatlong puntos na konektado sa pamamagitan ng lahat ng mga asul na linya. Ang numero ng Ramsey - ang pinakamaliit na bilang ng mga puntong kailangan namin upang gawin ito mangyari - ay anim.

Kapag tinitingnan ng mga mathematician ang isang problema, madalas nilang tanungin ang kanilang mga sarili: Nagmumungkahi ba ito ng isa pang tanong? Ito ang nangyari sa mga numero ng Ramsey - at mga problema sa partido.

Halimbawa, isa dito: Ang limang batang babae ay nagpaplano ng isang partido. Napagpasyahan nilang mag-imbita ng ilang mga lalaki sa partido, alam man nila ang mga lalaki o hindi. Gaano karaming mga lalaki ang kailangan nila upang mag-imbita upang matiyak na laging may tatlong lalaki sa kanila tulad na ang tatlo sa limang batang babae ay kaibigan sa lahat ng tatlong lalaki o hindi alam ang lahat ng tatlong lalaki? Marahil ay hindi madaling gumawa ng isang mahusay na hula sa sagot. Ito ay 41!

Napakakaunting mga numero ng Ramsey ay kilala. Gayunpaman, hindi ito huminto sa mga mathematician mula sa pagsisikap na malutas ang mga problemang iyon. Kadalasan, ang hindi pagtagumpayan ang isang problema ay maaaring humantong sa isang mas kawili-wiling problema. Ang ganito ang buhay ng isang dalub-agbilang.

Tungkol sa Ang May-akda

Gary Chartrand, Propesor Emeritus ng Matematika, Western Michigan University; Si Arthur Benjamin, Propesor ng Matematika, Harvey Mudd College, at Ping Zhang, Propesor ng Matematika, Western Michigan University

Ang artikulong ito ay orihinal na na-publish sa Ang pag-uusap. Basahin ang ang orihinal na artikulo.

Mga Kaugnay na Libro:

at InnerSelf Market at Amazon