قضیه رأی‌گیری برترند کیست؟ توضیح بده.
فرض کنید در یک انتخابات کاندید formula_1 ، formula_2رأی و کاندید formula_3 ، formula_4 رأی به دست می‌آورد؛ به طوری که formula_5formula_6 یک عدد صحیح مثبت است). تعداد (یا احتمال) حالاتی را به دست آورید که در تمام طول رأی‌گیری آرای formula_1، دست کم formula_6 تا بیشتر از آرای formula_3 باشد.پاسخ formula_10 است. (احتمال آن برای حالت formula_11 برابر با formula_12 است.)تاریخچه.در سال ۱۸۸۷ جوزف برترند که مسئلهٔ رأی‌گیری را بیان کرده‌بود برای حالت خاص formula_11 راه حلی از طریق روابط بازگشتی ارائه داد و خواستار راه حل مستقیمی برای آن شد. بلافاصله بعد از آن که برترند پرسش خود را مطرح کرد E ́mile Barbier راه‌حلی برای هر formula_6 اختیاری مطرح کرد اما هیچ اثباتی برای آن نداشت. اندکی بعد Désiré André اثبات ترکیبیاتی کوتاهی برای حالت formula_11 مسئلهٔ برترند داد. در سال ۱۹۲۳ Aeppli اعلام کرد که اولین اثبات برای قضیهٔ رأی‌گیری به ازای formula_16 دارد و به خوانندگان مشتاق مقالهٔ دکتری خود را پیشنهاد کرد.مثال.فرض کنید formula_11 است. ۵ رأی‌دهنده داریم که ۳نفر به formula_1 و ۲نفر به formula_3 رأی خواهند داد. (formula_20) می‌خواهیم در طول رأی‌گیری همواره تعداد رای‌های formula_1 بیشتر از formula_3 باشد. ۱۰ حالت برای ترتیب رأی‌ها وجود دارد:در جدول زیر تعداد آرای هر کاندید را در هر مرحله از رأی‌گیری برای حالت formula_31 بررسی می‌کنیم:برای هر ستون تعداد آرای A بیشتر از B است. برای حالت formula_27 در هر مرحله از رأی‌گیری داریم:در این حالت تعداد رأی‌های formula_3 در مرحلهٔ چهارم به formula_1 رسیده. از بین ۱۰حالت ممکن برای ترتیب آرا تنها در ۲حالت formula_24 و formula_23 همواره تعداد رای‌های formula_1 بیشتر از formula_3 است که برابر مقدارformula_41 می‌باشد.و احتمال آن formula_42 است که برابر formula_43 می‌باشد.اثبات با انعکاس برای حالت formula_11.آندره برای به دست آوردن تعداد حالت‌های مطلوب مسئله، حالت‌های نامطلوب را از تعداد کل حالات کم کرد. فرض کنید تعداد آرای کاندید formula_1 ، formula_2 تا و تعداد آرای کاندید formula_3 formula_4 تا باشد. می‌دانیم تمام جایگشت‌هایی که با formula_3 شروع شوند نامطلوبند. می‌خواهیم تناظر یک به یکی بین جایگشت‌های نامطلوبی که با formula_1 شروع می‌شوند و تمام جایگشت‌هایی که با formula_3 شروع می‌شوند برقرار کنیم.گره را نقطه‌ای تعریف می‌کنیم که تعداد رأی‌های formula_1 و formula_3 برابر باشند. اگر همواره آرای formula_1 بیشتر از formula_3 باشد نباید به گره‌ای برخورد کنیم. از آنجایی که تعداد رأی‌های formula_1 بیشتر از formula_3 است اگر رأی اول برای کاندید formula_3 باشد بالاخره به گره می‌رسیم. برای هر رشته که با formula_1 شروع شود و گره داشته باشد رأی‌ها را تا رسیدن به اولین گره معکوس می‌کنیم (یعنی هر formula_1 را به formula_3 تبدیل می‌کنیم و برعکس) و رشته‌ای که با formula_3 شروع می‌شود می‌سازیم. به‌طور مشابه هر رشته‌ای که با formula_3 شروع می‌شود را به رشته‌ای که با formula_1 شروع می‌شود و گره دارد (نامطلوب است) تبدیل می‌کنیم. (می‌دانیم معکوس معکوس هر رأی همان رأی است. اگر ۲تبدیل‌یافته یکسان باشند معکوس تا گرهٔ اول آن‌ها که همان رشته‌هایی هستند که از آنها به دست آمده‌اند هم یکسان اند پس این تبدیل‌ها یک به یک است) در نتیجه تناظری یک به یک داریم.تعداد حالاتی که با formula_3 شروع می‌شوند معادل جایگشت‌هایی است که می‌توان با formula_2 تا formula_1 و formula_68 تا formula_3 ساخت یعنی formula_70.در نتیجه تعداد حالات مطلوب از روابط زیر به‌دست می‌آید:formula_71و احتمال و قوع آن برابر formula_72 خواهدبود.تعمیم‌یافته: مجاز بودن تساوی آرا.مسئلهٔ اصلی یافتن احتمال آن است که همواره تعداد رأی‌های کاندید اول اکیداً بیشتر از کاندید دوم باشد. حال فرض کنید می‌خواهیم احتمال آن را به دست بیاوریم که هیچگاه تعداد رأی‌های کاندید دوم از کاندید اول بیشتر نشود (یعنی وجود گره مجاز باشد). در این حالت پاسخ برابر formula_73 خواهدبود.مسئلهٔ جدید را می‌توان با روش معکوس کردن مشابه مسئلهٔ اصلی حل نمود. تعداد کل رشته‌هایی که با formula_2 تا formula_1 و formula_4 تا formula_3 برای حالات رأی‌گیری می‌توان ساخت برابر است با : formula_78.هر رشتهٔ رأی‌گیری را به صورت مسیر شبکه ای روی صفحهٔ دکارتی نمایش می‌دهیم به‌طوری که:تناظر یک به یکی بین رشته‌ها و مسیرهای بین نقاط formula_81 و formula_82 با محدودیت حرکت به راست و بالا وجود دارد. یک رشته نامطلوب است اگر زمانی کاندید دوم رأی بیشتری از کاندید اول کسب کند یعنی مسیر متناظر آن از خط formula_83 عبور کرده و به خط formula_84 اصابت کند.نقطهٔ شروع تا اولین تلاقی هر مسیر نامطلوب با خط formula_84 را نسبت به خط مذکور قرینه می‌کنیم. مسیرهای جدید به دست آمده مسیری بین نقاط formula_86 و formula_87 خواهد بود. به‌طور مشابه با اثبات مسئلهٔ اصلی مسیرهای نامطلوب از formula_81 به formula_82 تناظر یک به یکی با مسیرهای بین نقاط formula_86 وformula_91 با محدودیت حرکت به راست و بالا دارند. تعداد این مسیرها formula_92 است پس تعداد مسیرهای مطلوب به صورت زیر به دست می‌آید:formula_93و احتمال وقوع آن برابر formula_94 خواهدبود.در حقیقت راه حل مسئله بالا و مسئلهٔ اصلی مرتبطند. برای اینکه تعداد رأی کاندید formula_1 همواره اکیداً بیشتر از کاندید formula_3 باشد باید رأی اول را formula_1 بیاورد و بعد از آن بدون در نظر گرفتن رأی اول، تعداد رأی‌هایش بزرگتر یا مساوی آرای formula_3 باشد پس مانند این است که مسئلهٔ بالا را با formula_99 رأی برای formula_1 و formula_4 رأی برای formula_3 حل کنیم:formula_103