сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

В игре «сет» участ­ву­ют все­воз­мож­ные че­ты­рех­знач­ные числа, со­сто­я­щие из цифр 1, 2, 3 (каж­дое число по од­но­му разу). Го­во­рят, что трой­ка чисел об­ра­зу­ет сет, если в каж­дом раз­ря­де либо все три числа со­дер­жат одну и ту же цифру, либо все три числа со­дер­жат раз­ные цифры. Слож­но­стью сета будем на­зы­вать ко­ли­че­ство таких раз­ря­дов, где все три цифры раз­лич­ны.

На­при­мер, числа 1232, 2213, 3221 об­ра­зу­ют сет слож­но­сти 3 (в пер­вом раз­ря­де встре­ча­ют­ся все три цифры, во вто­ром  — толь­ко двой­ка, в тре­тьем  — все три цифры, в чет­вер­том  — все три цифры); числа 1231, 1232, 1233  — сет слож­но­сти 1 (в пер­вых трех раз­ря­дах цифры сов­па­да­ют, и толь­ко в чет­вер­том все цифры раз­лич­ны). А числа 1123, 2231, 3311 во­об­ще не об­ра­зу­ют сета (в по­след­нем раз­ря­де встре­ча­ют­ся две еди­ни­цы и трой­ка).

Сетов какой слож­но­сти в игре боль­ше всего и по­че­му?

Спрятать решение

Ре­ше­ние.

За­ме­тим, что для любых двух чисел су­ще­ству­ет ровно один сет, в ко­то­ром они встре­ча­ют­ся. Дей­стви­тель­но, тре­тье число этого сета стро­ит­ся так: в тех раз­ря­дах, где пер­вые два числа сов­па­да­ют, тре­тье число имеет такую же цифру; в раз­ря­де, где пер­вые два числа раз­ли­ча­ют­ся, тре­тье число по­лу­ча­ет остав­шу­ю­ся цифру. На­при­мер, для чисел 1231 и 1223 тре­тьим в сете будет 1212.

Назовём «упо­ря­до­чен­ным сетом» сет из трёх четырёхзнач­ных чисел с учётом их по­ряд­ка. За­ме­тим, что каж­дый не­упо­ря­до­чен­ный сет  левая фи­гур­ная скоб­ка a, b, c пра­вая фи­гур­ная скоб­ка со­от­вет­ству­ет шести упо­ря­до­чен­ным:

 левая круг­лая скоб­ка а, b, c пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка a, c, b пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка b, a, c пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка b, c, a пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка c, a, b пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка c, b, a пра­вая круг­лая скоб­ка .

По­это­му вме­сто ко­ли­че­ства не­упо­ря­до­чен­ных сетов можно срав­ни­вать ко­ли­че­ство упо­ря­до­чен­ных (их в 6 раз боль­ше) од­но­знач­но опре­де­ля­ет­ся упо­ря­до­чен­ной парой чисел  левая круг­лая скоб­ка a, b пра­вая круг­лая скоб­ка .

По­счи­та­ем ко­ли­че­ство упо­ря­до­чен­ных сетов слож­но­сти k боль­ше 0. Каж­дый такой сет может на­чи­нать­ся про­из­воль­ным чис­лом a (81 ва­ри­ант). В этом числе нужно вы­брать k раз­ря­дов левая круг­лая скоб­ка C в сте­пе­ни k _4 спо­со­бов вы­бо­ра) и в каж­дом из них за­ме­нить цифру на одну из двух от­лич­ных от неё (2k спо­со­бов). В ре­зуль­та­те по­лу­чим число b, ко­то­рое од­но­знач­но опре­де­ля­ет сет. Итого по­лу­ча­ем 81 умно­жить на C_4 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка умно­жить на 2 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка упо­ря­до­чен­ных сетов слож­но­сти k.

Срав­ни­вая числа f левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка =C_4 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка умно­жить на 2 в сте­пе­ни левая круг­лая скоб­ка k пра­вая круг­лая скоб­ка для раз­ных k, по­лу­ча­ем: f левая круг­лая скоб­ка 1 пра­вая круг­лая скоб­ка =8, f левая круг­лая скоб­ка 2 пра­вая круг­лая скоб­ка =24, f левая круг­лая скоб­ка 3 пра­вая круг­лая скоб­ка =32, f левая круг­лая скоб­ка 4 пра­вая круг­лая скоб­ка =16. Как видим, наи­боль­шее ко­ли­че­ство сетов имеет слож­ность k=3.

 

Ответ: боль­ше всего сетов слож­но­сти 3.