Да, мисля че такова разбиване съществува. Да поставим единицата в едното подмножество. Тогава за произволно друго естествено число n, което се представя като произведение от прости множители така:
n = P1^A1*P2^A2* ... *Pn^An
да намерим общата сума на единците в двоичните представяния на числата A1, A2 ... An. Ако тази сума е четна, поставяме n в едно и също подмножество с 1, а ако е нечетна, го поставяме в другото подмножество.
Сега остава да покажем, че това разбиване на естетвените числа ни върши работа ( лесно се съобразява, че ако е така, то това е единственото възможно разбиване, защото ако допуснем, че има и друго, за най-малкото естествено число k, за което двете разбивания се различават, ще се получи разсинхронизация от 1 в броя представяния като произведение от различни числа, поради добавяне/премахване на варианта k=1*k). За целта е достатъчно за произволно естествено число n , да намерим взаимноеднозначно съответствие между представянията като
произведение от различни естетвени числа, за които горната сума е четна и тези, за които горната сума е нечтена.
Нека имаме едно такова представяне:
n = P1^A1*P2^A2* ... *Pn^An = k1*k2 = (P1^B1*P2^B2* ... *Pn^Bn)*(P1^C1*P2^C2* ... *Pn^Cn) ,
където Pi>Pj при i>j и k1 и k2 са с еднаква четност на горепосочената сума.
Тогава, понеже k1 е различно от k2, ще имаме най-малко i, за което Bi e разлчно от Ci, респективно ще имаме най-младши разряд, в който се различават двоичните представяния на Bi и Ci и ако в този разряд разменим стойностите на Bi и Ci, ще сменим четността на горепосочената сума за двата множителя, като запазим сумата Bi+Ci, а оттам и стойността на произведението - n.
Горното може и да не е вярно !
|