Ինչպե՞ս կարող են բոլորը ամուսնանալ (մեկ, երկսեռ և եռասեռ ամուսնություններ) մաթեմատիկական տեսանկյունից և ինչու են տղամարդիկ միշտ հաղթում

2012 թվականին տնտեսագիտության ոլորտում Նոբելյան մրցանակը շնորհվել է Լլոյդ Շեփլին և Էլվին Ռոթին։ «Կայուն բաշխման տեսության և շուկաների կազմակերպման պրակտիկայի համար». Ալեքսեյ Սավվաթեևը 2012 թվականին փորձել է պարզ և հստակ բացատրել մաթեմատիկոսների արժանիքների էությունը: Ձեր ուշադրությանն եմ ներկայացնում ամփոփում վիդեո դասախոսություններ.

Այսօր կլինի տեսական դասախոսություն։ Փորձերի մասին Էլա Ռոտա, մասնավորապես նվիրատվության հետ կապված, չեմ ասի։

Երբ հայտարարվեց, որ Լլոյդ Շեփլի (1923-2016) ստացել է Նոբելյան մրցանակ, կար ստանդարտ հարց. «Ինչպե՞ս: Նա դեռ ողջ է!?!?” Նրա ամենահայտնի արդյունքը ստացվել է 1953թ.

Ֆորմալ կերպով բոնուսը տրվել է այլ բանի համար։ 1962 թվականին «Ամուսնության կայունության թեորեմի» վերաբերյալ իր աշխատության համար՝ «Քոլեջ ընդունելություն և ամուսնության կայունություն»:

Կայուն ամուսնության մասին

Համապատասխանող (համապատասխանեցում) - համապատասխանություն գտնելու խնդիր:

Կա որոշակի մեկուսացված գյուղ։ Կան «մ» երիտասարդներ և «մ» աղջիկներ: Մենք պետք է նրանց ամուսնացնենք միմյանց հետ: (Պարտադիր չէ, որ նույն թիվը, գուցե վերջում ինչ-որ մեկը մենակ մնա):

Ի՞նչ ենթադրություններ պետք է արվեն մոդելում: Որ պատահականորեն նորից ամուսնանալը հեշտ չէ: Ազատ ընտրության ուղղությամբ որոշակի քայլ է արվում. Ասենք՝ կա մի իմաստուն աքսակալ, ով ուզում է նորից ամուսնանալ, որ մահից հետո ամուսնալուծություններ չսկսվեն։ (Ամուսնալուծությունը մի իրավիճակ է, երբ ամուսինն ավելի շատ ցանկանում է, որ երրորդ կողմի կինը լինի իր կին, քան իր կինը):

Այս թեորեմը ժամանակակից տնտեսագիտության ոգով է: Նա բացառիկ անմարդկային է: Տնտեսագիտությունը ավանդաբար անմարդկային է եղել։ Տնտեսագիտության մեջ մարդուն փոխարինում է մեքենան՝ առավելագույնի հասցնելու շահույթը: Այն, ինչ ես ձեզ կասեմ, բարոյական տեսանկյունից բացարձակ խենթ բաներ են։ սրտին մոտ մի ընդունեք:

Տնտեսագետներն ամուսնությանն այսպես են նայում.
m1, m2,… mk - տղամարդիկ:
w1, w2,... wL - կանայք:

Տղամարդուն նույնացնում են նրանով, թե ինչպես է «պատվիրում» աղջիկներին. Գոյություն ունի նաև «զրոյական մակարդակ», որից ցածր կանանց ընդհանրապես չի կարելի առաջարկել որպես կին, նույնիսկ եթե ուրիշներ չլինեն։

Ամեն ինչ տեղի է ունենում երկու ուղղությամբ, աղջիկների դեպքում՝ նույնը։

Նախնական տվյալները կամայական են։ Միակ ենթադրությունը/սահմանափակումն այն է, որ մենք չենք փոխում մեր նախասիրությունները:

Թեորեմ. Անկախ բաշխվածությունից և զրոյական մակարդակից, միշտ կա մի տարբերակ ստեղծելու մեկ առ մեկ համապատասխանություն որոշ տղամարդկանց և որոշ կանանց միջև, որպեսզի այն ամուր լինի բոլոր տեսակի բաժանումների համար (ոչ միայն ամուսնալուծությունների):

Ի՞նչ սպառնալիքներ կարող են լինել:

Կա մի զույգ (մ, վ), որը ամուսնացած չէ: Բայց w-ի համար ներկայիս ամուսինը m-ից վատն է, իսկ m-ի համար ներկայիս կինը w-ից վատն է: Սա անկայուն վիճակ է։

Կա նաև տարբերակ, որ ինչ-որ մեկն ամուսնացած է եղել «զրոյից ցածր» մեկի հետ, այս իրավիճակում ամուսնությունը նույնպես կփլվի:

Եթե ​​կինն ամուսնացած է, բայց նախընտրում է չամուսնացած տղամարդու, ում համար նա զրոյից բարձր է։

Եթե ​​երկու հոգի երկուսն էլ ամուսնացած չեն, և երկուսն էլ միմյանց համար «զրոյից բարձր» են:

Ենթադրվում է, որ ցանկացած նախնական տվյալների համար գոյություն ունի ամուսնության նման համակարգ, որը դիմացկուն է բոլոր տեսակի սպառնալիքներին: Երկրորդ՝ նման հավասարակշռություն գտնելու ալգորիթմը շատ պարզ է։ Համեմատենք M*N-ի հետ։

Այս մոդելը ընդհանրացվեց և ընդարձակվեց մինչև «բազմակնություն» և կիրառվեց շատ ոլորտներում:

Գեյլ-Շեյպլի ընթացակարգ

Եթե ​​բոլոր տղամարդիկ և բոլոր կանայք հետևեն «դեղատոմսերին», արդյունքում ամուսնության համակարգը կայուն կլինի:

Դեղատոմսեր.
Անհրաժեշտության դեպքում մի քանի օր ենք վերցնում: Մենք ամեն օր բաժանում ենք երկու մասի (առավոտյան և երեկոյան):

Առաջին առավոտ յուրաքանչյուր տղամարդ գնում է իր լավագույն կնոջ մոտ և թակում պատուհանը՝ խնդրելով ամուսնանալ իր հետ։

Նույն օրը երեկոյան հերթը հասնում է կանանց, ի՞նչ կարող է բացահայտել կինը։ Որ նրա պատուհանի տակ ամբոխ էր՝ կամ մեկը, կամ ոչ մի տղամարդ։ Նրանք, ովքեր այսօր ոչ ոք չունեն, շրջանցում են իրենց հերթը և սպասում: Մնացածները, ովքեր ունեն առնվազն մեկը, ստուգում են տղամարդկանց, ովքեր գալիս են տեսնելու, որ նրանք «զրոյից բարձր են»: Գոնե մեկը ունենալ։ Եթե ​​դուք բոլորովին անհաջողակ եք, և ամեն ինչ զրոյից ցածր է, ապա բոլորին պետք է ուղարկել: Կինն ընտրում է եկածներից ամենամեծին, ասում է, որ սպասի, մնացածին ուղարկում է։

Մինչև երկրորդ օրը իրավիճակն այսպիսին է՝ որոշ կանայք ունեն մեկ տղամարդ, ոմանք՝ ոչ:

Երկրորդ օրը բոլոր «ազատ» (ուղարկված) տղամարդիկ պետք է գնան երկրորդ առաջնահերթ կնոջ մոտ: Եթե ​​այդպիսի մարդ չկա, ապա տղամարդը հայտարարվում է ամուրի։ Այն տղամարդիկ, ովքեր արդեն նստած են կանանց հետ, դեռ ոչինչ չեն անում։

Երեկոյան կանայք նայում են իրավիճակին. Եթե ​​մեկին, ով արդեն նստած էր, միացել է ավելի բարձր առաջնահերթություն, ապա ավելի ցածր առաջնահերթությունը ուղարկվում է: Եթե ​​նրանք, ովքեր գալիս են, ավելի ցածր են, քան արդեն հասանելի է, բոլորին ուղարկում են: Կանայք ամեն անգամ ընտրում են առավելագույն տարրը։

Կրկնում ենք.

Արդյունքում, յուրաքանչյուր տղամարդ անցել է իր կանանց ամբողջ ցուցակը և կամ մնացել է մենակ, կամ նշանվել ինչ-որ կնոջ հետ: Հետո բոլորին կամուսնացնենք։

Հնարավո՞ր է այս ամբողջ գործընթացը վարել, բայց կանայք վազեն տղամարդկանց մոտ: Գործընթացը սիմետրիկ է, բայց լուծումը կարող է տարբեր լինել: Բայց հարցն այն է, թե ո՞վ է ավելի լավ դրանից:

Թեորեմ. Դիտարկենք ոչ միայն այս երկու սիմետրիկ լուծումները, այլև բոլոր կայուն ամուսնական համակարգերի ամբողջությունը: Բնօրինակ առաջարկվող մեխանիզմը (տղամարդիկ առաջադրվում են, իսկ կանայք ընդունում/հրաժարվում են) հանգեցնում է ամուսնության համակարգի, որն ավելի լավ է ցանկացած տղամարդու համար, քան ցանկացած այլ, և ավելի վատ, քան ցանկացած այլ կնոջ համար:

Նույնասեռ ամուսնությունները

Նկատի առ «միասեռ ամուսնությունների» հետ կապված իրավիճակը։ Դիտարկենք մի մաթեմատիկական արդյունք, որը կասկածի տակ է դնում դրանց օրինականացման անհրաժեշտությունը։ Գաղափարապես ոչ ճիշտ օրինակ.

Դիտարկենք չորս համասեռամոլների a, b, c, d.

առաջնահերթությունները a. bcd
առաջնահերթությունները b:cad
առաջնահերթությունները գ՝ աբդ
դ-ի համար կարևոր չէ, թե նա ինչպես է դասակարգում մնացած երեքը:

Հաստատում Այս համակարգում չկա կայուն ամուսնության համակարգ:

Քանի՞ համակարգ կա չորս հոգու համար: Երեք. ab cd, ac bd, ad bc. Զույգերը կփլուզվեն, և գործընթացը կգնա ցիկլերով։

«Եռասեռ» համակարգեր.
Սա ամենակարեւոր հարցն է, որը բացում է մաթեմատիկայի մի ամբողջ դաշտ։ Դա արել է Մոսկվայի իմ գործընկեր Վլադիմիր Իվանովիչ Դանիլովը։ Նա «ամուսնությունը» դիտում էր որպես օղի խմելու, իսկ դերերը հետևյալն էին. Այն իրավիճակում, երբ յուրաքանչյուր դերի 4 կամ ավելի ներկայացուցիչ կա, դա անհնար է լուծել բիրտ ուժով։ Կայուն համակարգի հարցը բաց է։

Շեյփլի վեկտոր

Տնակային գյուղում որոշել են ասֆալտապատել ճանապարհը։ Ներս մտնելու կարիք կա: Ինչպե՞ս:

Այս խնդրի լուծումը Շապլին առաջարկել է 1953 թվականին։ Ենթադրենք կոնֆլիկտային իրավիճակ մի խումբ մարդկանց հետ N={1,2…n}: Ծախսերը/օգուտները պետք է կիսվեն: Ենթադրենք, մարդիկ միասին ինչ-որ օգտակար բան են արել, վաճառել այն և ինչպե՞ս բաժանել շահույթը։

Շապլին առաջարկեց, որ բաժանելիս պետք է առաջնորդվենք նրանով, թե որքան կարող են ստանալ այդ մարդկանց որոշակի ենթաբազմություններ։ Որքա՞ն գումար կարող են վաստակել բոլոր 2N ոչ դատարկ ենթաբազմությունները: Եվ այս տեղեկատվության հիման վրա Շապլին գրել է ունիվերսալ բանաձեւ.

Օրինակ. Մոսկվայի ստորգետնյա անցումում նվագում են մենակատար, կիթառահար և թմբկահար։ Երեքը ժամում 1000 ռուբլի են վաստակում։ Ինչպե՞ս բաժանել այն: Հնարավոր է հավասարապես:
V(1,2,3)=1000

Եկեք այդպես ձևացնենք
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100

Արդար բաժանումը չի կարող որոշվել, քանի դեռ մենք չիմանանք, թե ինչ շահույթ է սպասվում տվյալ ընկերությանը, եթե այն անջատվի և գործի ինքնուրույն: Իսկ երբ որոշեցինք թվերը (համագործակցային խաղը սահմանեցինք բնորոշ ձևով).

Սուպերհավելվածությունն այն է, երբ նրանք միասին ավելի շատ են վաստակում, քան առանձին-առանձին, երբ միավորվելն ավելի ձեռնտու է, բայց պարզ չէ, թե ինչպես կարելի է բաժանել շահումները: Այս մասին բազմաթիվ օրինակներ են կոտրվել։

Կա խաղ. Երեք գործարարներ միաժամանակ 1 մլն դոլարի ավանդ են գտել. Եթե ​​երեքով համաձայն են, ուրեմն միլիոնն է։ Ցանկացած զույգ կարող է սպանել (հեռացնել գործից) և իր համար ստանալ ամբողջ միլիոնը։ Եվ ոչ ոք միայնակ ոչինչ չի կարող անել։ Սա սարսափելի կոոպերատիվ խաղ է՝ առանց լուծումների: Միշտ կլինեն երկու հոգի, ովքեր կարող են վերացնել երրորդին... Համագործակցային խաղերի տեսությունը սկսվում է լուծում չունեցող օրինակով։

Մենք այնպիսի լուծում ենք ուզում, որ ոչ մի կոալիցիա չցանկանա արգելափակել ընդհանուր լուծումը։ Բոլոր ստորաբաժանումների հավաքածուն, որոնք հնարավոր չէ արգելափակել, միջուկն է: Պատահում է, որ միջուկը դատարկ է։ Բայց եթե նույնիսկ դատարկ չէ, ինչպե՞ս բաժանել։

Շեյփլին առաջարկում է բաժանել այսպես. Նետեք մետաղադրամ n-ով: եզրեր. Մենք բոլոր խաղացողներին գրում ենք այս հերթականությամբ: Ասենք առաջին թմբկահարը։ Նա ներս է մտնում և վերցնում իր 100-ը: Հետո մտնում է «երկրորդը», ասենք մենակատարը: (Դհոլահարի հետ նրանք կարող են վաստակել 450, թմբկահարն արդեն վերցրել է 100) Մենակատարը վերցնում է 350: Մտնում է կիթառահարը (միասին 1000, -450), վերցնում է 550: Շատ հաճախ հաղթում է վերջինը: (Սուպերմոդուլյարություն)

Եթե ​​բոլոր պատվերների համար գրենք.
GSB - (հաղթում C) - (հաղթում D) - (հաղթում B)
SGB ​​- (հաղթում C) - (հաղթում D) - (հաղթում B)
SBG - (հաղթում C) - (հաղթում D) - (հաղթում B)
BSG - (հաղթում C) - (հաղթում D) - (հաղթում B)
BGS - (շահույթ C) - (շահույթ D) - (շահույթ B)
GBS - (հաղթում C) - (հաղթում D) - (հաղթում B)

Եվ յուրաքանչյուր սյունակի համար մենք ավելացնում և բաժանում ենք 6-ի` միջինը բոլոր պատվերների վրա. սա Շեյփլի վեկտոր է.

Շեյփլին ապացուցեց թեորեմը (մոտավորապես). Գոյություն ունի խաղերի դաս (սուպերմոդուլային), որտեղ հաջորդ մարդը, ով միանում է մեծ թիմին, ավելի մեծ հաղթանակ է բերում նրան: Միջուկը միշտ դատարկ չէ և միավորների ուռուցիկ համակցություն է (մեր դեպքում՝ 6 միավոր)։ Շեյպլի վեկտորը գտնվում է միջուկի հենց կենտրոնում: Դա միշտ էլ կարելի է որպես լուծում առաջարկել, ոչ ոք դեմ չի լինի։

1973 թվականին ապացուցվեց, որ քոթեջների խնդիրը սուպերմոդուլային է։

Բոլոր n մարդիկ կիսում են ճանապարհը դեպի առաջին քոթեջ: Մինչև երկրորդը՝ n-1 մարդ։ և այլն:

Օդանավակայանը ունի թռիչքուղի։ Տարբեր ընկերություններ տարբեր երկարությունների կարիք ունեն: Նույն խնդիրն է առաջանում.

Կարծում եմ, որ նրանք, ովքեր Նոբելյան մրցանակ են շնորհել, նկատի ունեին այս վաստակը, և ոչ միայն մարժայի խնդիրը:

Thank you!

Ещё

• «Մաթեմատիկա - պարզ» ալիք. youtube.com/punkmathematics
• «Սավվատեև առանց սահմանների» ալիք՝ eduex.ru, brainsex.ru, studfuck.ru
• Հանրային «Մաթեմատիկան պարզ է». vk.com/alexei_savvateev
• Հանրային «Մաթեմատիկոսները կատակում են». vk.com/bsu_mmf_jokes
• Կայք, այնտեղ բոլոր դասախոսությունները +100 դաս և ավելին՝ savvateev.xyz

Source: www.habr.com