سلام.

میایم و از استقرا روی تنوع عدد ها استفاده میکنم.حالتی که فقط یک نوع عدد داریم که یا نمیشه این کارو کرد یا فقط به یه حالت میشه.

میایم کوچکترین عدد رو در نظر میگیریم.فرض کنید $ 2^k$ باشه. میدونیم که سایر عدد ها به $ 2^{k+1}$ بخش پذیرن. اگه یه دونه $ 2^k$ داشته باشیم که تعداد حالت های افراز 0 تاست چون هر جور که افراز انجام بشه مجموع اعداد یه دسته به $ 2^{k+1}$ بخش پذیره و مجموع اعداد دسته دیگه به $ 2^{k+1}$ ، دقیقا $ 2^{k}$ تا باقی مونده داره پس برابر نیستن.

حالا فرض کنید دوتا $ 2^{k}$ داشته باشیم.دوحالت افراز داریم :

• هر دو $ 2^{k}$دریک دسته قرار بگیرند.
• دوتا $ 2^{k}$ تو دوتا دسته مختلف قرار بگیرن.

اول اثبات میکنیم دوحالت بالا همزمان رخ نمیدن.$x$ رو مجموع اعداد درنظر میگیریم.چون سایر عدد ها به $ 2^{k+1}$ بخش پذیرن اگه تو یه افراز هر دو تا $ 2^{k}$ در یه دسته قرار بگیرن $\frac{x}{2}\equiv 0\pmod {2^{k+1}} $ و اگه تو یه افراز دو تا $2^{k}$ در دو دسته مختلف قرار بگیرن داریم $\frac{x}{2}\equiv {2^{k}} \pmod {2^{k+1}} $ که با قبلی در تناقضه.پس حداکثر یکی از حالت های بالا پیش میاد.

اگه حالت دوم پیش بیاد مکان دو تا $ 2^{k}$به طور یکتا معلوم میشه و بقیه طبق فرض به توانی از 2 یا 0 حالت افراز میشن.پس حکم برقراره. پس فرض کنید حالت اول پیش بیاد و تو همه افراز ها دو تا $ 2^{k}$ کنار هم بیان.

اول دوتا $ 2^{k}$ رو برمیداریم و به جاش یدونه $ 2^{k+1}$قرار میدیم. اگه درحالت جدید 3 تا یا یه دونه $ 2^{k+1}$ داشته باشیم ثابت میکنیم هیچ افراز معتبری در این حالت وجود نداره. یه افراز با 3 تا $ 2^{k+1}$ رو در نظر بگیرین.دو حالت داره:

• هر سه تا $ 2^{k+1}$دریک دسته قرار بگیرند.
• دوتا $ 2^{k+1}$ تو یه دسته قرار بگیرن و اون یکی توی یه دسته دیگه.

چون سایر عدد ها به $ 2^{k+2}$ بخش پذیرن هر کدوم از حالت های بالا رو که در نظر بگیریم از یه دسته نتیجه میگیریم $\frac{x}{2}\equiv 0\pmod {2^{k+2}} $ و از دسته دیگه نتیجه میگیریم $\frac{x}{2}\equiv {2^{k+1}} \pmod {2^{k+2}} $ که نشون میده مجموع دودسته با هم برابر نیست.پس افراز معتبر نیست.

همچنین حالتی که یدونه $ 2^{k+1}$ داریم هم به طور مشاب هیچ افرازی نداره.پس فرض کنید دقیقا دوتا $ 2^{k+1}$ داشته باشیم.همونطوری که گفتیم یا دو تاشون در دو دسته مختلف قرار میگیرن که به دو طرف مقدار ثابتی اضافه میکنن پس با بقیه کاری ندارن و طبق فرض به توانی از 2 حالت افراز میشن و بقیه هم به توانی از 2 حالت افراز میشن و ضرب دوتا توان 2 ، توان 2 است ، یا دوتاشون در یه دسته قرار میگیرن که دوباره حذفشون میکنیم و به جاشون یه عدد به اندازه جمعشون میزاریم و دوباره همین کارها رو میکنیم.اگه تو یه مرحله متوقف بشیم که حله در غیر این صورت میرسیم به بزرگترین وزنه(که 2 تا ازش داریم و یکیشون از جمع قبلیا ساخته شده.).واضحه که همه قبلیا باید تو یه دسته قرار بگیرن و این عدد بزرگه توی دسته دیگه.پس عدد بزرگه رو میزاریم و از فرض استفاده میکنیم.

قبول دارم یه ذره عجیب غریب شد!

موفق باشید!