اصلاحیه تمرین تقریبی

در مورد سوال max k-cut تمرین‌ها بود.

اشکال ایده‌ای که گفتند این بود که تعداد یالهای بین دو مجموعه توزیع یکنواخت ندارند که احتمال آنها به سادگی حساب شود. (در صورتی که یالها را تصادفی بین مجموعه‌ها تقسیم می‌کردیم این جواب درست بود.)

در مورد ایده‌ی خودم هم احتمال حضور هر یال:

(k^2-k)/(k^2) = (k-1)/k = 1-1/k

می‌شود که در نتیجه جواب قبلی غلط است.

اما از آنجا که k>=2 است نتیجه می‌گیریم که مقدار بالا از ۱/۲ بیشتر است و حکم ثابت می‌شود.