Երբ են կեղծ մետաղադրամները հարևան

«Քվանտ», 2025, 5-6, 30

Ա. ԳՐԻԲԱԼԿՈ, Կ. ԿՆՈՊ

Այս հոդվածում մենք կներկայացնենք «Քվանտ» ամսագրի խնդրագրքի M2833 դժվար խնդրի լուծումը։ Դիտարկենք խնդրի ընհանրացված ձևակերպումը։

Շրջանագծով դասավորված են արտաքնապես իրար նման N մետաղադրամներ։ Հայտնի է, որ դրանցից երկուսը կեղծ են։ Իսկական մետաղադրամները նույն քաշն ունեն, կեղծերը՝ նույնպես, բայց նրանք ավելի թեթև են իսկականներից։ Պահանջվում է նժարավոր կշեռքի միջոցով, առանց կշռաքարերի, K կշռումով պարզել՝ արդյո՞ք կեղծ մետաղադրամները կողք կողքի (հարևան) են դրված։

Դրանից բացի, ցանկալի կլիներ հասկանալ, թե մետաղադրամների առավելագույն ինչ N թվի դեպքում է հնարավոր դա անել K կշռումով։

Նշենք, որ այս խնդրի տարբերակները հանդիպել են նաև նախկինում. K= 2, N=8 դեպքը տե՛ս «Քվանտիկ» №9, 2023 թ. (էջ 22, խնդիր 3), K=3, N= 20 դեպքը տե՛ս «Քվանտ» №9, 2023 թ. (էջ 39, խնդիր 16)։

Վերջապես, M2833 խնդրում պահանջվում է գտնել ալգորիթմ K= 3 և ա) N= 26, բ) N =30 դեպքերի համար։

Մետաղադրամները համարակալենք ժամասլաքի ուղղությամբ՝ 1-ից մինչև N թվերով։ Այն մետաղադրամները, որոնց կեղծ կամ իսկական լինելը դեռևս ապացուցված չէ, ավանդաբար, կանվանենք կասկածելի։ Մեր խնդրում կասկածելի մետաղադրամները բաժանվում են երկու խմբի. նրանք, որոնք դեռևս կարող են կեղծ լինել իրենց հարևան մետաղադրամներից որևէ մեկի հետ միասին, և նրանք, որոնք արդեն չունեն այդպիսի հնարավորություն։

Դիտարկվող դեպքերից յուրաքանչյուրի համար կբերենք լուծման մի քանի ալգորիթմներ՝ դրանց բազմազանությունն ընդգծելու համար։

Դեպք K = 1, N = 4

Մեկ կշռումով հաջողվում է լուծել խնդիրը N > 4
— մետաղադրամների համար՝ կշռման հետևյալ եղանակով.

• {1, 3} ? {2, 4}

Եթե կշռման արդյունքում ստացվում է հավասարություն, ապա խնդրի պատասխանն է «այո», այսինքն՝ կեղծ մետաղադրամները հարևան են, իսկ եթե անհավասարություն է, ապա` «ոչ»։

Մեկ այլ հնարավոր ալգորիթմ է՝

• {1} ? {3}

Այս արդյունքի բարելավելի չլինելը կարելի է ապացուցել բոլոր հնարավոր տարբերակների քննարկումով։

Դեպք K = 2, N = 8

Այս արդյունքը նույնպես կարող է ստացվել տարբեր ալգորիթմներով. ներկայացնենք դրանցից երկուսը։

Առաջին ալգորիթմ

Առաջին կշռում․

• {2, 3} ? {6, 7}

1. Հավասարության դեպքում ({2, 3} = {6, 7})՝ պարզ է, որ կշեռքի յուրաքանչյուր նժարին առկա է հավասար թվով կեղծ մետաղադրամ (0-ական կամ 1-ական)։ Ընդ որում, 2, 3, 6, 7 մետաղադրամները մնում են կասկածելի, բայց դրանցից ոչ մեկը չի կարող կեղծ լինել իր հարևանի հետ միասին։ Որպես հարևան կեղծ մետաղադրամներ մեզ մոտ կարող են լինել միայն երկու զույգ՝ (4, 5) և (8, 1)։ Երկրորդ կշռումով կարելի է համեմատել այդ զույգերը միմյանց հետ.
   • {4, 5} ? {8, 1}

Այժմ, {4, 5} = {8, 1} հավասարությունից հետո հանգում ենք «ոչ» պատասխանին, իսկ անհավասարության դեպքում հասկանում ենք, որ առկա է կեղծ մետաղադրամ, ինչը նշանակում է, որ ոչ առաջին կշռման մետաղադրամների մեջ, ոչ էլ ավելի ծանր նժարի վրա կեղծ մետաղադրամներ չկան։ Հետևաբար, երկու կեղծ մետաղադրամներն էլ ավելի թեթև նժարի վրա են, այսինքն՝ կարող ենք տալ «այո» պատասխանը։

2. Անհավասարության դեպքում՝ առանց ընդհանրությունը խախտելու ենթադրենք, թե {2, 3} < {6, 7}։ Այստեղից հասկանում ենք, որ 2 և 3 մետաղադրամների թվում կա կա՛մ մեկ կեղծ մետաղադրամ, կա՛մ երկուսն էլ կեղծ են։ Առաջին դեպքում հարևան կեղծ մետաղադրամների զույգեր կարող են լինել {1, 2}-ը և {3, 4}-ը։ Այդ ժամանակ երկրորդ կշռումը կլինի.
   • {1, 3} ? {2, 4}

Դրանում ստացված հավասարությունն ապացուցում է, որ երկու կեղծ մետաղադրամներն էլ կշեռքի վրա են, ինչպես նաև այն, որ կեղծերի զույգը հարևան երեք զույգերից մեկն է, կամ {1, 4} զույգը։ Սակայն վերջին դեպքն անհնար է, ուստի կշեռքի հավասարությունը նշանակում է «այո» պատասխան հիմնական խնդրին։ Այսպիսով, երկրորդ կշռման ժամանակ անհավասարությունը նշանակում է «ոչ»։

Երկրորդ ալգորիթմ

Առաջին կշռում.

• {2, 3} ? {5, 8}

1. Հավասարության դեպքում՝ հարևան կեղծ մետաղադրամների միակ հնարավոր զույգը {6, 7}-ն է։ Ընդ որում, 6 և 7 մետաղադրամների մասնակցությամբ կեղծ մետաղադրամների մյուս հնարավոր զույգերը չեն պարունակում 2, 3, 5, 8 մետաղադրամները, այսինքն՝ պարտադիր պարունակում են 1 և 4 մետաղադրամներից մեկը։ Ուստի հավասարությունից հետո երկրորդ կշռումով կարելի է համեմատել՝
   • {6, 7} ? {1, 4}

և {6, 7} < {1, 4} դեպքում տալ «այո» պատասխանը, իսկ ցանկացած այլ արդյունքի դեպքում՝ «ոչ»։

2. Անհավասարության դեպքերը ({2, 3} ≠ {5, 8})՝ այստեղ տարբեր են.
   • ա) Եթե ձախ նժարն ավելի թեթև է, ապա 2 և 3 մետաղադրամներից առնվազն մեկը կեղծ է, և այդ ժամանակ երկրորդ կշռումով կարելի է վարվել ինչպես առաջին ալգորիթմում՝ {1, 3} ? {2, 4}։
   • բ) Եթե ավելի թեթև է աջ նժարը, ապա 2-ը և 3-ը իսկական մետաղադրամներ են, իսկ հարևան կեղծ մետաղադրամների հնարավոր զույգեր են մնացել {4, 5}-ը, {5, 6}-ը, {7, 8}-ը, {8, 1}-ը, ուստի երկրորդ կշռումով կարելի է համեմատել։
   • {4, 5, 6} ? {1, 7, 8}

Հավասարությունն ակնհայտորեն նշանակում է «ոչ» պատասխան։ Ապացուցենք, որ անհավասարություններից յուրաքանչյուրը նշանակում է «այո» պատասխան։ Իրոք, կշեռքի վրա են բոլոր 6 կասկածելի մետաղադրամները, ուստի անհավասարություն լինում է միայն այն ժամանակ, երբ երկու կեղծ մետաղադրամներն էլ գտնվում են նույն նժարին։ Ձախ նժարի վրայի ոչ հարևան մետաղադրամներն են 4-ը և 6-ը, իսկ աջ նժարինը՝ 1-ը և 7-ը։ Բայց այս զույգերից ոչ մեկում չկան առաջին կշռման այն մետաղադրամները, որոնք ավելի թեթև էին (այսինքն՝ 5-ը կամ 8-ը)։ Նշանակում է՝ այդպիսի զույգերը չեն կարող կեղծ լինել։

Ծանոթագրություն։ Առաջարկված ալգորիթմները տարբեր կերպ են բաժանում հարևան մետաղադրամների 8 հնարավոր զույգերի բազմությունը առաջին կշռման արդյունքների միջև։ Առաջին ալգորիթմի համար այդ հարաբերակցությունը 2 : 3 : 3 է, իսկ երկրորդի համար՝ 1 : 3 : 4։ Այն փաստը, որ երկրորդ կշռման ժամանակ հնարավոր է «ճանաչել» հարևանության չորս տարբերակ, հույս է տալիս խնդիրը լուծել 10 մետաղադրամի համար՝ արդյունքները բաժանելով 2 : 4 : 4 կամ 3 : 3 : 4 հարաբերությամբ։ Փորձե՛ք ինքնուրույն հորինել այդ ալգորիթմը։

Դեպք K = 3, N = 20

Առաջին ալգորիթմ

Առաջին կշռում.

• {1, 2, 3, 4, 5, 6} ? {11, 12, 13, 14, 15, 16}

1. Եթե ստացվի հավասարություն, ապա միայն սպիտակ մետաղադրամները կարող են լինել հարևան կեղծեր։ Այնուհետև խնդիրը լուծվում է այնպես, ինչպես 8 մետաղադրամի համար նախատեսված առաջին ալգորիթմում՝
   • {8, 9} ? {18, 19} և այլն։
2. Եթե ստացվի անհավասարություն, ապա առանց ընդհանրությունը խախտելու կհամարենք, որ աջ նժարն ավելի ծանր է։ Այդ դեպքում խնդիրը լուծում ենք 8 մետաղադրամի առաջին ալգորիթմի համանմանությամբ՝ շարքով դասավորված 20-ից մինչև 7 մետաղադրամների համար։ Միակ նրբությունն այն է, որ եթե {1, 2} ≠ {5, 6}, ապա հարևան կեղծ մետաղադրամների զույգը կարող է լինել միայն {3, 4}-ը, բայց մենք չգիտենք՝ մեկ կեղծ մետաղադրամ կա՞, թե՞ երկու {20, 1, 2, 3, 4, 5, 6, 7} խմբում։ Ուստի ստուգման համար 3, 4 մետաղադրամներին ավելացնում ենք ակնհայտորեն իսկական մետաղադրամներ և կատարում երրորդ կշռումը.
   • {3, 4, 11, 12, 13, 14, 15, 16} ? {7, 8, 9, 10, 17, 18, 19, 20}

Երկրորդ ալգորիթմ

Առաջին կշռում.

• {2, 4, 6, 8, 10} ? {12, 14, 16, 18, 20}

Եթե ստացվի հավասարություն, ապա պատասխանն անմիջապես «ոչ» է։ Եթե անհավասարություն է, ապա առանց ընդհանրությունը խախտելու կհամարենք, որ

 (2,4,6,8,10) < (12,14,16,18,20), այդ դեպքում երկրորդ կշռումը՝ (1,5,9) ? (3,7,11)

Եթե այստեղ ստացվի հավասարություն, ապա պատասխանը նորից «ոչ» է։ Եթե անհավասարություն է, ապա ենթադրենք, առանց ընդհանրությունը խախտելու, ավելի թեթև է (1,5,9) նժարը։ Այդ դեպքում հարևան կեղծ մետաղադրամների հնարավոր զույգերը միայն հետևյալներն են՝ (1,2), (4,5), (5,6), (8,9) և (9,10)։

Կատարենք երրորդ կշռումը՝ (5,8,10) ? (4,6,9) :

Հավասարությունը կնշանակի, որ կշեռքի վրա կա կա՛մ երկու կեղծ մետաղադրամ, կա՛մ ոչ մի հատ։ Երկու դեպքում էլ պատասխանը «այո» է։ Անհավասարությունը նշանակում է «ոչ» պատասխան։

Այժմ լուծենք խնդիրը 26 մետաղադրամի համար։

Դեպք K=3, N=26

Առաջին կշռումը (նկ. 3)՝ (2,4,6,8,10) ? (12,14,16,18,20)

1) Եթե անհավասարություն է, ենթադրենք առանց ընդհանրությունը խախտելու աջ նժարն ավելի ծանր է։ Այդ դեպքում 2, 4, 6, 8, 10 մետաղադրամների մեջ հաստատ կա առնվազն մեկ կեղծ մետաղադրամ, իսկ հարևան կեղծերի զույգերը կարող են լինել միայն 1-ից մինչև 11-ը։

Կատարում ենք երկրորդ կշռումը՝ (1,5,9) ? (3,7,11)

• 1.1) Եթե հավասարություն է, ապա 1, 3, 5, 7, 9, 11 մետաղադրամները իսկական են, և պատասխանը «ոչ» է։
• 1.2) Եթե անհավասարություն է, ապա` ենթադրենք առանց ընդհանրությունը խախտելու (1,5,9) < (3,7,11)։ Այդ դեպքում երկրորդ կեղծ մետաղադրամը 1, 5, 9-ի մեջ է, իսկ հարևան կեղծերի զույգերը կարող են լինել (1,2), (4,5), (5,6), (8,9), (9,10)։ Կատարում ենք երրորդ կշռումը՝ (5,8,10) ? (4,6,9) Եթե հավասարություն է, ապա կա՛մ կշեռքի բոլոր մետաղադրամները իսկական են (նշանակում է՝ կեղծ են 1-ը և 2-ը), կա՛մ յուրաքանչյուր նժարին կա մեկական կեղծ մետաղադրամ (այդ դեպքում դրանք կարող են լինել (4,5), (5,6), (8,9), (9,10) զույգերը)։ Ամեն դեպքում պատասխանը «այո» է։ Մնացած բոլոր դեպքերում անհավասարություն է, և պատասխանը՝ «ոչ»։

2) Եթե հավասարություն է, ապա կա՛մ յուրաքանչյուր նժարին կա մեկական կեղծ մետաղադրամ (և այդ դեպքում պատասխանն անմիջապես «ոչ» է), կա՛մ կշեռքի բոլոր մետաղադրամներն իսկական են, և այդ ժամանակ հարևան կեղծերի զույգերը կարող են լինել միայն 21-ից մինչև 1-ը։

Կատարում ենք երկրորդ կշռումը (նկ. 4)՝ (22,23) ? (25,26)

• 2.1) Եթե հավասարություն է, ապա պատասխանը «ոչ» է։
• 2.2) Եթե անհավասարություն է, ենթադրենք, առանց ընդհանրությունը խախտելու, (22,23) < (25,26)։ Այդ դեպքում 22, 23 մետաղադրամների մեջ հաստատ կա առնվազն մեկ կեղծ մետաղադրամ, իսկ հարևան կեղծերի զույգերը կարող են լինել միայն 21-ից մինչև 24-ը։

Կատարում ենք երրորդ կշռումը՝ (22,24) ? (21,23) Եթե հավասարություն է, ապա յուրաքանչյուր նժարին կա մեկական կեղծ մետաղադրամ (ընդ որում` դա (21,24) զույգը չէ), և պատասխանը «այո» է։ Հակառակ դեպքում պատասխանը «ոչ» է։

Վերջապես, դիտարկենք 30 մետաղադրամի դեպքը։

Դեպք K=3, N=30

Առաջին կշռումը (նկ. 5)՝ (1,3,5,7,9,11) ? (20,22,24,26,28,30)

1) Եթե հավասարություն է, ապա կա՛մ կշեռքի բոլոր մետաղադրամներն իսկական են, կա՛մ յուրաքանչյուր նժարին կա մեկական կեղծ մետաղադրամ, ուստի հարևան կեղծերի զույգերը կարող են լինել կա՛մ 12-ից մինչև 19-ը, կա՛մ 30-ը և 1-ը։

Նշանակենք (3,5,7,9,11) մետաղադրամների բազմությունը R-ով, (20,22,24,26,28) բազմությունը՝ L-ով (սրանք առաջին կշռման մետաղադրամների խմբերն են՝ առանց 1 և 30 մետաղադրամների), (2,4,6,8,10) բազմությունը՝ R’-ով, իսկ (21,23,25,27,29) բազմությունը՝ L’-ով (սրանք առաջին կշռման խմբերի ներսում գտնվող մետաղադրամների խմբերն են)։

Կատարում ենք երկրորդ կշռումը (նկ. 6)՝ (1,13,14) ? (17,18,30)

• 1.1) Եթե հավասարություն է՝ (1,13,14) = (17,18,30), ապա կասկածելի զույգեր են մնում (15,16)-ը և (30,1)-ը։ Ընդ որում, նկատենք, որ եթե 1 կամ 30 մետաղադրամներից մեկը կեղծ է, ապա մյուսն էլ է կեղծ, քանի որ միայն դրանք են մասնակցել երկու կշռումներին էլ։ Կատարում ենք երրորդ կշռումը՝ (R,L,13,14) ? (R’,L’,12,19)
  • Եթե ստացվի հավասարություն՝ (R,L,13,14) = (R’,L’,12,19), ապա կշեռքի բոլոր մետաղադրամները իսկական են։ Իրոք, եթե կեղծ մետաղադրամ լիներ R կամ L խմբերից մեկում, ապա երկրորդ կեղծը կլիներ դրանցից մյուսում։ Իսկ եթե կեղծ լիներ 13-ը կամ 14-ը, ապա երկրորդ կեղծը կլիներ 17-ը կամ 18-ը, որոնք աջ նժարին չկան։ Հետևաբար, 17 և 18 մետաղադրամները նույնպես իսկական են, և պատասխանն այս դեպքում «այո» է։
  • Եթե (R,L,13,14) < (R’,L’,12,19), ապա նույն պատճառներով կա՛մ երկու կեղծ մետաղադրամներն էլ R և L խմբերում են, կա՛մ կեղծերից մեկը 13-ն է կամ 14-ը, իսկ երկրորդը՝ 17-ը կամ 18-ը։ Ամեն դեպքում պատասխանը «ոչ» է։
  • Եթե (R,L,13,14) > (R’,L’,12,19), ապա 13 և 14 մետաղադրամները իսկական են, ինչը նշանակում է, որ 17-ը և 18-ը նույնպես իսկական են, բայց աջ նժարի վրա կա առնվազն մեկ կեղծ մետաղադրամ, ուստի պատասխանը «ոչ» է։
• 1.2) Եթե անհավասարություն է, ապա առանց ընդհանրությունը խախտելու ենթադրենք, որ (1,13,14) < (17,18,30)։ Այդ դեպքում 17, 18, 30 մետաղադրամները իսկական են, իսկ 1, 13, 14 մետաղադրամների մեջ հաստատ կա առնվազն մեկ կեղծ։ Կատարում ենք երրորդ կշռումը (միանգամից նկատենք, որ կշեռքի վրա կա առնվազն մեկ կեղծ մետաղադրամ, իսկ աջ նժարի 30-ը իսկական է)՝ (1,12,14) ? (13,15,30)
  • Եթե հավասարություն է՝ (1,12,14) = (13,15,30), ապա 1 մետաղադրամը չի կարող կեղծ լինել (հակառակ դեպքում երկրորդ կեղծը կլիներ L խմբից, իսկ աջ նժարին այդ խմբից մետաղադրամ չկա)։ Նշանակում է՝ կա՛մ կեղծ է 13-ը (և այդ դեպքում երկրորդը 12-ն է կամ 14-ը), կա՛մ կեղծ է 14-ը (և այդ դեպքում երկրորդը 13-ն է կամ 15-ը)։ Ուստի, ամեն դեպքում պատասխանը «այո» է։
  • Եթե (1,12,14) < (13,15,30), ապա կա՛մ 1 մետաղադրամն է կեղծ, կա՛մ 14-ը, բայց 13 և 15 մետաղադրամներն իսկական են, ուստի ամեն դեպքում պատասխանը «ոչ» է։
  • Եթե (1,12,14) > (13,15,30), ապա 13 մետաղադրամը կեղծ է, բայց 12-ը և 14-ը իսկական են, հետևաբար պատասխանը նույնպես «ոչ» է։

2) Եթե անհավասարություն է, ապա առանց ընդհանրությունը խախտելու կհամարենք, որ
(1,3,5,7,9,11) < (20,22,24,26,28,30)։ Այդ դեպքում 20, 22, 24, 26, 28, 30 մետաղադրամները իսկական են, իսկ 1, 3, 5, 7, 9, 11 մետաղադրամների մեջ հաստատ կա առնվազն մեկ կեղծ, ուստի հարևան կեղծերի զույգերը կարող են լինել միայն 1-ից մինչև 12-ը։

Կատարում ենք երկրորդ կշռումը (աջ նժարին ավելացնում ենք իսկական 20 մետաղադրամը) (նկ. 7)՝ (2,6,10) ? (4,8,20)

• 2.1) Եթե հավասարություն է, ապա 2, 4, 6, 8, 10 մետաղադրամները իսկական են, և մնում է ստուգել միայն մեկ կասկածելի զույգ՝ (11, 12)։ Կատարում ենք երրորդ կշռումը (աջ նժարին ավելացնում ենք չորս իսկական մետաղադրամներ՝ 20, 22, 24, 26)՝ (1,3,5,7,9) ? (12,20,22,24,26)
  • Եթե հավասարություն է՝ (1,3,5,7,9) = (12,20,22,24,26), ապա կա՛մ 12 մետաղադրամը իսկական է, կա՛մ այն կեղծ է և 1, 3, 5, 7, 9 մետաղադրամներից մեկը նույնպես կեղծ է, բայց այդ դեպքում 11 մետաղադրամը իսկական է, ուստի ամեն դեպքում պատասխանը «ոչ» է։
  • Եթե (1,3,5,7,9) < (12,20,22,24,26), ապա 12 մետաղադրամը իսկական է, և պատասխանը նույնպես «ոչ» է։
  • Եթե (1,3,5,7,9) > (12,20,22,24,26), ապա 12 մետաղադրամը կեղծ է, իսկ 1, 3, 5, 7, 9 մետաղադրամները՝ իսկական, հետևաբար 11 մետաղադրամը կեղծ է, և պատասխանը՝ «այո»։
• 2.2) Եթե (2,6,10) < (4,8,20), ապա երկրորդ կեղծ մետաղադրամը 2, 6, 10-ի մեջ է։ Կատարում ենք երրորդ կշռումը՝ (1,3,10) ? (2,9,11) :Եթե հավասարություն է, ապա կա՛մ կշեռքի բոլոր մետաղադրամները իսկական են (և այդ դեպքում կեղծ մետաղադրամները 6-ն է և 5 կամ 7 մետաղադրամներից մեկը), կա՛մ կեղծ է 2-ը (և այդ դեպքում երկրորդը 1 կամ 3 մետաղադրամներից մեկն է), կա՛մ կեղծ է 10-ը (և այդ դեպքում երկրորդը 9 կամ 11 մետաղադրամներից մեկն է)։ Ամեն դեպքում պատասխանը «այո» է։ Եթե անհավասարություն է, ապա առանց ընդհանրությունը խախտելու համարենք, որ (1,3,10) < (2,9,11)։ Այդ դեպքում 2, 9, 11 մետաղադրամները իսկական են, իսկ կեղծ մետաղադրամներից մեկը 1, 3, 10-ի մեջ է, ուստի պատասխանը «ոչ» է։
• 2.3) Եթե (2,6,10) > (4,8,20), ապա երկրորդ կեղծ մետաղադրամը 4-ն է կամ 8-ը։ Կատարում ենք երրորդ կշռումը (միանգամից նկատենք, որ կշեռքի վրա կա առնվազն մեկ կեղծ մետաղադրամ)՝ (3,5,8) ? (4,7,9) :Եթե հավասարություն է, ապա կա՛մ կեղծ է 4 մետաղադրամը (և այդ դեպքում երկրորդը 3 կամ 5 մետաղադրամներից մեկն է), կա՛մ կեղծ է 8 մետաղադրամը (և այդ դեպքում երկրորդը 7 կամ 9 մետաղադրամներից մեկն է)։ Ամեն դեպքում պատասխանը «այո» է։ Եթե անհավասարություն է առանց ընդհանրությունը խախտելու՝ (3,5,8) < (4,7,9), ապա 8 մետաղադրամը կեղծ է, իսկ 7 և 9 մետաղադրամները՝ իսկական, ուստի պատասխանը «ոչ» է։

Ի վերջո ասենք, թե ինչ է հայտնի այն մետաղադրամների առավելագույն թվի վերաբերյալ, որոնցից K կշռումների ընթացքում հնարավոր է պարզել՝ արդյոք երկու հարևան կեղծերը կողք կողքի են գտնվում։ Այդ թիվը նշանակենք N_max(K)-ով։

Մեկ կշռման դեպքի համար, ինչպես արդեն ասվել է վերևում, տարբերակների քննարկմամբ կարելի է ապացուցել, որ N_max(1)=4: K=2-ի համար ապացուցված է, որ N_max(2)=10: Փորձե՛ք դա ապացուցել ինքնուրույն։ K=3 և K=4 դեպքերի համար հայտնի է միայն, որ N_max(3) >= 38, իսկ N_max(4) >= 181: Այս խնդրի վերաբերյալ այլ բովանդակալից արդյունքներ հայտնի չեն։

Թարգմանությունը՝ Ռուզան Խաչատրյանի