Kuunganisha ramani kwenye shindig yako inayofuata. unclibraries_ kawaida 

Wacha tuseme unapanga sherehe yako ijayo na inaumiza juu ya orodha ya wageni. Unapaswa kutuma mialiko kwa nani? Je! Ni mchanganyiko gani wa marafiki na wageni ni mchanganyiko sahihi?

Inageuka kuwa wanahisabati wamekuwa wakifanya kazi kwenye toleo la shida hii kwa karibu karne moja. Kulingana na kile unachotaka, jibu linaweza kuwa ngumu.

Kitabu chetu, "Ulimwengu wa Kuvutia wa Nadharia ya Grafu, ”Inachunguza mafumbo kama haya na inaonyesha jinsi ya kutatuliwa kupitia grafu. Swali kama hili linaweza kuonekana dogo, lakini ni onyesho zuri la jinsi grafu zinaweza kutumiwa kutatua shida za kihesabu katika nyanja anuwai kama sayansi, mawasiliano na jamii.

Puzzles huzaliwa

Ingawa inajulikana kuwa Harvard ni moja ya vyuo vikuu vya juu vya masomo nchini, unaweza kushangaa kujua kwamba kulikuwa na wakati ambapo Harvard ilikuwa na moja ya timu bora za kitaifa za mpira wa miguu. Lakini mnamo 1931, ikiongozwa na Robo-robo yote wa Amerika Barry Wood, ndivyo ilivyokuwa kesi.

Msimu huo Harvard alicheza Jeshi. Wakati wa mapumziko, bila kutarajia, Jeshi liliongoza Harvard 13-0. Akiwa amekasirika wazi, rais wa Harvard alimwambia kamanda wa jeshi wa cadet kwamba wakati Jeshi linaweza kuwa bora kuliko Harvard katika mpira wa miguu, Harvard alikuwa bora katika mashindano ya wasomi zaidi.

Ingawa Harvard alirudi kushinda Jeshi 14-13, kamanda huyo alikubali changamoto ya kushindana dhidi ya Harvard katika jambo la kisomi zaidi. Ilikubaliwa kuwa wawili hao watashindana - katika hesabu. Hii ilisababisha Jeshi na Harvard kuchagua timu za hesabu; pambano hilo lilitokea West Point mnamo 1933. Kwa mshangao wa Harvard, Jeshi lilishinda.

Ushindani wa Jeshi la Harvard mwishowe ulisababisha mashindano ya hesabu ya kila mwaka kwa wahitimu wa kwanza mnamo 1938, iitwayo Mtihani wa Putnam, aliyetajwa kwa William Lowell Putnam, jamaa wa rais wa Harvard. Mtihani huu ulibuniwa kuchochea ushindani mzuri katika hesabu huko Merika na Canada. Kwa miaka iliyopita na kuendelea hadi leo, mtihani huu umekuwa na shida nyingi za kupendeza na zenye changamoto nyingi - pamoja na ile tunayoelezea hapo juu.

Mstari mwekundu na bluu

Mtihani wa 1953 ulikuwa na shida ifuatayo (ilibadilishwa jina kidogo): Kuna alama sita kwenye ndege. Kila hatua imeunganishwa na kila hatua nyingine na laini ambayo ni ya samawati au nyekundu. Onyesha kuwa kuna alama tatu kati ya hizo ambazo ni mistari ya rangi moja tu iliyochorwa.

Katika hesabu, ikiwa kuna mkusanyiko wa alama na mistari iliyochorwa kati ya jozi kadhaa za alama, muundo huo unaitwa grafu. Utafiti wa grafu hizi huitwa nadharia ya grafu. Katika nadharia ya grafu, hata hivyo, alama zinaitwa vipeo na mistari inaitwa kingo.

Grafu zinaweza kutumiwa kuwakilisha hali anuwai. Kwa mfano, katika shida hii ya Putnam, hoja inaweza kumwakilisha mtu, laini nyekundu inaweza kumaanisha watu ni marafiki na laini ya samawati inamaanisha kuwa wao ni wageni.

Onyesha kuwa kuna alama tatu zimeunganishwa na mistari ya rangi moja. Gary Chartrand

Kwa mfano, wacha tuita alama A, B, C, D, E, F na uchague moja yao, sema A. Kati ya mistari mitano iliyochorwa kutoka A hadi alama zingine tano, lazima kuwe na mistari mitatu ya rangi moja.

Sema mistari kutoka A hadi B, C, D zote ni nyekundu. Ikiwa laini kati ya mbili za B, C, D ni nyekundu, basi kuna alama tatu na mistari nyekundu tu kati yao. Ikiwa hakuna laini kati ya mbili za B, C, D ni nyekundu, basi zote ni bluu.

Je! Ikiwa kuna alama tano tu? Kunaweza kuwa hakuna alama tatu ambapo mistari yote kati yao ime rangi sawa. Kwa mfano, mistari A-B, B-C, C-D, D-E, E-A inaweza kuwa nyekundu, na nyingine bluu.

Kutokana na kile tulichokiona, basi, idadi ndogo kabisa ya watu ambao wanaweza kualikwa kwenye sherehe (ambapo kila watu wawili ni marafiki au wageni) kama kwamba kuna marafiki watatu wa pamoja au watatu ambao hawafahamiani ni sita.

Je! Ikiwa tungependa watu wanne wawe marafiki wa pamoja au wageni? Je! Ni idadi ndogo ya watu gani lazima tuwaalika kwenye sherehe ili kuwa na hakika ya hii? Swali hili limejibiwa. Ni miaka 18.

Je! Ikiwa tungependa watu watano wawe marafiki wa pamoja au wageni? Katika hali hii, idadi ndogo zaidi ya watu wa kualika kwenye sherehe kuhakikishiwa hii haijulikani. Hakuna anayejua. Ingawa shida hii ni rahisi kuelezea na labda inasikika rahisi, ni ngumu sana.

Nambari za Ramsey

Kile ambacho tumekuwa tukijadili ni aina ya nambari katika nadharia ya grafu inayoitwa nambari ya Ramsey. Nambari hizi zimetajwa kwa mwanafalsafa wa Uingereza, mchumi na mtaalam wa hesabu Frank Plumpton Ramsey.

Ramsey alikufa akiwa na umri wa miaka 26 lakini alipata nadharia ya kushangaza sana katika hesabu, katika umri wake mdogo sana, ambayo ilileta swali letu hapa. Sema tuna ndege nyingine iliyojaa alama zilizounganishwa na laini nyekundu na bluu. Tunachagua nambari mbili chanya, zilizoitwa r na s. Tunataka kuwa na alama r haswa ambapo mistari yote kati yao ni nyekundu au s alama ambapo mistari yote kati yao ni ya samawati. Je! Ni idadi ndogo zaidi ya alama ambazo tunaweza kufanya na hii? Hiyo inaitwa nambari ya Ramsey.

Kwa mfano, tuseme tunataka ndege yetu iwe na angalau alama tatu zilizounganishwa na laini zote nyekundu na alama tatu zilizounganishwa na laini zote za bluu. Nambari ya Ramsey - idadi ndogo zaidi ya alama tunayohitaji kufanya hii kutokea - ni sita.

Wanahisabati wanapoangalia shida, mara nyingi hujiuliza: Je! Hii inapendekeza swali lingine? Hii ndio iliyotokea na idadi ya Ramsey - na shida za chama.

Kwa mfano, hii ni moja: Wasichana watano wanapanga sherehe. Wameamua kuwaalika wavulana kwenye sherehe, ikiwa wanawajua wavulana au la. Je! Wanahitaji kualika wavulana wangapi ili kuhakikisha kwamba kutakuwa na wavulana watatu kati yao hivi kwamba wasichana watatu kati ya watano ni marafiki wa wavulana wote watatu au hawajui wavulana wote watatu? Labda sio rahisi kufikiria vizuri jibu. Ni miaka 41!

Nambari chache za Ramsey zinajulikana. Walakini, hii haizuii wanahisabati kujaribu kutatua shida kama hizo. Mara nyingi, kutosuluhisha shida moja kunaweza kusababisha shida ya kupendeza zaidi. Ndio maisha ya mtaalam wa hesabu.

kuhusu Waandishi

Gary Chartrand, Profesa Mtaalam wa Hisabati, Michigan Western University; Arthur Benjamin, Profesa wa Hisabati, Harvey Mudd College, na Ping Zhang, Profesa wa Hisabati, Michigan Western University

Makala hii ilichapishwa awali Mazungumzo. Soma awali ya makala.

Vitabu kuhusiana:

at InnerSelf Market na Amazon