Огра­ни­чим свер­ху число n сле­ду­ю­щим об­ра­зом. Сна­ча­ла за­ме­тим, что за три взве­ши­ва­ния на ча­шеч­ных весах можно по­лу­чить толь­ко 27 ре­зуль­та­тов (так как за каж­дое одно взве­ши­ва­ние на ча­шеч­ных весах можно по­лу­чить толь­ко 3 ре­зуль­та­та  — левая чашка легче пра­вой, чашки урав­но­ве­ше­ны, пра­вая чашка легче левой). Но так как ко­ли­че­ство ва­ри­ан­тов фаль­ши­вой мо­не­ты (из n) и ее от­но­си­тель­но­го веса (легче или тя­же­лее) равно 2n, то долж­но вы­пол­нять­ся не­ра­вен­ство Сле­до­ва­тель­но, Но (см. за­да­чу 6725) не­воз­мож­но за 3 взве­ши­ва­ния на ча­шеч­ных весах найти среди 13 монет един­ствен­ную фаль­ши­вую (от­лич­но­го от осталь­ных весом) и од­но­вре­мен­но опре­де­лить ее от­но­си­тель­ный вес. По­это­му надо рас­смот­реть

В опи­са­нии спо­со­ба (ал­го­ритм) опре­де­ле­ния фаль­ши­вой мо­не­ты будем ис­поль­зо­вать сле­ду­ю­щие обо­зна­че­ния:

а)  мо­не­ты будем обо­зна­чать (1), (2), ... (12);

б)  вы­ра­же­ния вида для взве­ши­ва­ния, в ко­то­ром, в дан­ном слу­чае, пара монет р и q по­ме­ще­ны на левую чашку весов, а пара дру­гих монет r и s (тоже из монет и гирь­ки)  — на пра­вую;

в)  у взве­ши­ва­ния может быть три ис­хо­да: < (если левая чашка легче),  =  (если чашки урав­но­ве­ше­ны) и > (если пра­вая чашка легче).

Те­перь мы можем дать ком­мен­ти­ро­ван­ное опи­са­ние спо­со­ба (ал­го­рит­ма), ко­то­рый по­лу­ча­ет 12 монет (1)..(12), среди ко­то­рых ровно одна фаль­ши­вая имеет вес, от­лич­ный от веса дру­гих на­сто­я­щих монет рав­но­го веса, и опре­де­ля­ет фаль­ши­вую мо­не­ту и ее от­но­си­тель­ный вес за три взве­ши­ва­ния на ча­шеч­ных весах:

1)  = (то есть фаль­ши­вая среди (9)...(12), а все (1)..(8)  — на­сто­я­щие): case ((1)+(9))?((10)+(11)) of:

1.1) = (то есть фаль­ши­вая (12)): case ((1))?((12)):

1.1.1) <: фаль­ши­вая мо­не­та (12) и тя­же­лее;

1.1.2) >: фаль­ши­вая мо­не­та (12) и легче;

1.2) < (то есть фаль­ши­вая среди (9) и легче или среди (10) и (11) и тя­же­лее): case ((10))?((11)):

1.2.1) = (воз­мож­но толь­ко если (9) фаль­ши­вая и легче): фаль­ши­вая мо­не­та (9) и легче;

1.2.2) < (воз­мож­но толь­ко если (11) фаль­ши­вая и тя­же­лее): фаль­ши­вая мо­не­та (11) и тя­же­лее;

1.2.3) > (воз­мож­но толь­ко если (10) фаль­ши­вая и тя­же­лее): фаль­ши­вая мо­не­та (10) и тя­же­лее;

1.3) > (то есть фаль­ши­вая среди (9) и тя­же­лее или среди (10) и (11) и легче): саsе ((10))?((11)):

1.3.1) = (воз­мож­но толь­ко если (9) фаль­ши­вая и тя­же­лее): фаль­ши­вая мо­не­та (9) и тя­же­лее;

1.3.2) < (воз­мож­но толь­ко если (10) фаль­ши­вая и легче): фаль­ши­вая мо­не­та (10) и легче;

1.3.3) > (воз­мож­но толь­ко если (11) фаль­ши­вая и легче): фаль­ши­вая мо­не­та (11) и легче;

2)  < (то есть фаль­ши­вая среди (1)..(4) и легче, или среди (5)..(8) и тя­же­лее, а все (9)..(12) на­сто­я­щие):

2.1) = (то есть фаль­ши­вая среди (4) и легче, или (7) и (8) и тя­же­лее, а все осталь­ные мо­не­ты  — на­сто­я­щие): case ((7))?((8)) of:

2.1.1) = (воз­мож­но толь­ко если фаль­ши­вая (4) и легче): фаль­ши­вая мо­не­та (4) и легче;

2.1.2) < (воз­мож­на толь­ко если фаль­ши­вая (8) и тя­же­лее): фаль­ши­вая мо­не­та (8) и тя­же­лее;

2.1.3) > (воз­мож­на толь­ко если фаль­ши­вая (7) и тя­же­лее): фаль­ши­вая мо­не­та (7) и тя­же­лее;

2.2) < (воз­мож­но толь­ко если фаль­ши­вая среди (1) и (2) и легче): case ((1))?((2)) of:

2.2.1) < (воз­мож­на толь­ко если фаль­ши­вая (1) и легче): фаль­ши­вая мо­не­та (1) и легче;

2.2.2) > (воз­мож­на толь­ко если фаль­ши­вая (2) и легче): фаль­ши­вая мо­не­та (2) и легче;

2.3) > (воз­мож­но толь­ко если фаль­ши­вая среди (3) и легче, или среди (5) и (6) и тя­же­лее): саsе ((5))?((6)) of:

2.3.1) = (воз­мож­на толь­ко если фаль­ши­вая (3) и легче): фаль­ши­вая мо­не­та (3) и легче;

2.3.2) < (воз­мож­на толь­ко если фаль­ши­вая (6) и тя­же­лее): фаль­ши­вая мо­не­та (6) и тя­же­лее;

2.3.3) > (воз­мож­на толь­ко если фаль­ши­вая (5) и тя­же­лее): фаль­ши­вая мо­не­та (5) и тя­же­лее;

3)  > то есть фаль­ши­вая среди (1)..(4) и тя­же­лее, или среди (5)..(8) и легче, а все (9)...(12) на­сто­я­щие):

3.1) то есть фаль­ши­вая среди (4) и тя­же­лее, или (7) и (8) и легче, а все осталь­ные мо­не­ты на­сто­я­щие): case ((7))?((8)) of:

3.1.1) = (воз­мож­но толь­ко если фаль­ши­вая (4) и тя­же­лее): фаль­ши­вая мо­не­та (4) и тя­же­лее;

3.1.2) < (воз­мож­на толь­ко если фаль­ши­вая (7) и легче): фаль­ши­вая мо­не­та (7) и легче;

3.1.3) > (воз­мож­на толь­ко если фаль­ши­вая (8) и легче): фаль­ши­вая мо­не­та (8) и легче;

3.2) < (воз­мож­но толь­ко если фаль­ши­вая среди (3) и тя­же­лее или (5) и (6) и легче): case ((5))?((6)) of:

3.2.1) = (воз­мож­но толь­ко если фаль­ши­вая (3) и тя­же­лее): фаль­ши­вая мо­не­та (3) и тя­же­лее;

3.2.2) < (воз­мож­на толь­ко если фаль­ши­вая (5) и легче): фаль­ши­вая мо­не­та (5) и легче;

3.2.3) > (воз­мож­на толь­ко если фаль­ши­вая (6) и легче): фаль­ши­вая мо­не­та (6) и легче;

3.3) > (воз­мож­но толь­ко если фаль­ши­вая среди (1) и (2) и тя­же­лее): case ((1))((2)) of:

3.3.1) < (воз­мож­на толь­ко если фаль­ши­вая (2) и тя­же­лее): фаль­ши­вая мо­не­та (2) и тя­же­лее;

3.3.2) > (воз­мож­на толь­ко если фаль­ши­вая (1) и тя­же­лее): фаль­ши­вая мо­не­та (1) и тя­же­лее.

Кор­рект­ность и пол­но­та спо­со­ба (ал­го­рит­ма) сле­ду­ет из опи­са­ния ал­го­рит­ма и ком­мен­та­ри­ев.

Ответ: