بین تعداد رشته های n تایی با a,b,c,d که در آن ها تعداد a ها با تعداد b ها برابر است و تعداد دنباله های دودویی به 2n که در آن ها تعداد یک ها با تعداد صفر ها برابر است یک نگاشت دوسویی به شکل زیر برقرار میکنیم:

a:11
b:00
c:10
d:01

یعنی این که به ازای هر a در دنباله 11 را جایگزین میکنیم،به ازای هر b در دنباله 00 را، به ازای هر c در دنباله 10 را و به ازای هر d در دنباله 01 را.

مثال برای n=2 در شکل زیر آمده است:

واضح است هر دنباله دارای تعداد مساوی 0 و 1 است چرا که تعداد a ها و b ها با هم برابر است پس تعداد 00 ها با تعداد 11 ها برابر است.تعداد c و d ها نیز مهم نیست چرا که به ازای هر c یا d یکی به تعداد 0 ها و یکی به تعداد 1 ها اضافه میشود.پس از هر دنباله با حروف به طول n که تعداد a ها با تعداد b ها در آن برابر است میتوان به یک دنباله با 0 و1 به طول 2n رسید که تعداد 0 ها و 1ها در آن برابر است.

از طرفی از هر دنباله با 0 و1 به طول 2n که تعداد 0 ها و 1ها در آن برابر است نیز به دقیقا یک رشته از a,b,c,d میرسیم که تعداد b ها و a ها در آن برابر است.چرا که کافی است به روش زیر عمل کنیم:

از ابتدای دنباله شروع کرده و دو رقم دو رقم جلو میرویم.اگر دو رقم 00 بودند b ، اگر 11 بودند a، اگر 01 بودند d و اگر 10 بودند c را جایگزین آن ها میکنیم.

پس به ازای هر رشته از حروف به یک رشته از 0 و 1 و به ازای هر رشته از 0 و 1 به یک رشته از حروف میرسیم. بنابراین تعداد اعضای این دو مجموعه با هم برابر است و حکم اثبات میشود.

موفق باشید!

این سوال سوال Division 1 سایت CodeForces بوده راهشو اونجا بخونید سوالش الگوریتمیه حلشم اونجا هست اگه میشه سعی کنید سوال در حد مرحله 2 بزارین این سوالا وقت گیره 4 تا حلقه می خوره حلشم فقط با برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه برنامه نویسیه