موضوع مقاله: قضیه هیلز–جووت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه هیلز–جووت | مقدمه: این دو نفر می‌خواستند نشان دهند که اشیاء با ابعاد بالا، باید ساختار ترکیبیاتی قانونمندی داشته باشند و ممکن نیست که خواص چنین اشیائی به‌طور کامل رندوم و تصادفی باشد.Alfred W. | ## بخش 1: قضیه هیلز–جووت | یک توصیف نادقیق هندسی از قضیه این است که برای هر دو عدد صحیح مثبت مانند و عددی مانند وجود دارد که، اگر خانه‌های یک شبکهٔ مکعبی بعدی ، با رنگ، رنگ شوند، باید سطر، ستون یا قطری وجود داشته باشد که همهٔ خانه‌های آن یکرنگ هستند. به بیانی دیگر، برای نسخهٔ تعمیم یافته از بازی ایکس-او تایی، عدد وجود دارد که اگر این بازی در مکعب بعدی انجام شود، بازی هرگز مساوی نخواهد شد! مهم نیست که چقدر بزرگ باشد یا این که چند بازیکن در بازی شرکت می‌کنند و کدام یک از در کدام نوبت بازی خواهد کرد! با استفاده از استدلال استراتژی دزدی، شاید کسی فکر کند که اگر دو بازیکن یکی درمیان بازی کنند، آنگاه نفر اول برای های به اندازهٔ کافی بزرگ، استراتژی برد خواهد داشت، با این حال تا به الان الگوریتمی عملی برای اجرای این استراتژی شناخته نشده‌است! برای توصیف دقیق تر، را مجموعهٔ کلمات به طول روی یک الفبای حرفی تعریف می‌کنیم که این الفبا همان مجموعهٔ می‌باشد، و با این تعریف تمام کلمات حرفی این الفبا عضو هستند! این مجموعه، ابرمکعبی که موضوع قضیه است را شکل می‌دهد .(در واقع اینطور تصور می‌کنیم که هر کلمه آدرس یک خانه از این ابر مکعب است) یک کلمهٔ متغیر مانند روی کلمه‌ای است که در جای حداقل یکی از حروف آن متغیر قرار دارد. کلمات یک خط ترکیبیاتی را در فضای تشکیل می‌دهند، خطوط ترکیبیاتی شامل سطرها، ستون‌ها و بعضی از اقطار ابرمکعب می‌باشند، قضیه هیلز جووت بیان می‌کند که برای اعداد داده شدهٔ و ، عدد مثبت و صحیح وجود دارد که وابسته به و است و برای هر افراز به دسته، حداقل یک دسته وجود دارد که یک خط ترکیبیاتی به‌طور کامل عضو آن دسته است! برای مثال قرار می‌دهیم: n=3, c=2,H=۳، ابر مکعب به دست آمده در این حالت خاص، در واقع همان صفحهٔ بازی معروف ایکس-او است! ۱۱ ۱۲ ۱۳ ۲۱ ۲۲ ۲۳ ۳۱ ۳۲ ۳۳ به‌طور مثال کلمهٔ را در نظر بگیرید، با قرار دادن ۱٬۲،۳ به جای متغیر خط ۲۱ ۲۲ ۲۳ به دست می‌آید. یا برای مثال کلمهٔ متغیر را در نظر بگیرید، به قرار دادن ۱٬۲،۳ به جای ، خط ترکیبیاتی یا همان قطر ۱۱ ۲۲ ۳۳ به دست می‌آید.(توجه کنید که در بازی ایکس-او، اگر تمام قطر ۱۳ ۲۲ ۳۱ توسط یکی از بازیکنان علامت گذاری شود، آن بازیکن برنده می‌شود، اما این خط، یک خط ترکیبیاتی نیست. | ## بخش 2: قضیه هیلز–جووت | در این حالت امکان‌پذیر است که خانه‌ها را به دو دسته افراز کنیم (به‌طور مثال {۱۱٬۲۲٬۲۳٬۳۱} و {۱۲٬۱۳٬۲۱٬۳۲٬۳۳ که هیچکدام از دسته‌ها شامل یک خط ترکیبیاتی نباشند.(در واقع در این حالت بازی مساوی می‌شود!) از طرف دیگر اگر H را به عدد ۸ افزایش دهیم ،(دقت کنید که تعداد خانه‌های زمین بازی در این حالت برابر با ۳۸ = ۶۵۶۱ می‌شود!) و این زمین بازی را به دو دسته تقسیم کنیم (همان "ضربدر" و" دایره"های مشهور که در بازی استفاده می‌شود!)، یکی از دسته‌ها حتماً شامل یک خط ترکیبیاتی است .(یا به عبارتی بازی مساوی نمی‌شود!) برای اثبات پایین را نگاه کنید. اثبات قضیه در حالتی خاص اکنون به اثبات قضیه هیلز–جووت در حالت خاص که در بالا بحث شد می‌پردازیم. ایده این است که این حکم را به اثبات حالات ساده‌تر قضیه هیلز–جووت کاهش دهیم.(در این حالت خاص منظور و است.) حالت کلی قضیه هیلز–جووت را می‌توان با روشی مشابه با استفاده از استقرای ریاضی اثبات کرد. هر عضو ابرمکعب رشته‌ای از هشت عدد از ۱ تا ۳ است مثلاً ۱۳۲۱۱۳۲۱ یک عضو ابرمکعب است. ما برای اثبات از برهان خلف استفاده می‌کنیم و فرض می‌کنیم که نه دسته دایره‌ها و نه دسته ضربدرها شامل خط ترکیبیاتی نیستند. اگر ما ۶ عضو اینچنین رشته‌ای را ثابت بگیریم و ۲ عضو اخر را متغیر فرض کنیم یک صفحه بازی ایکس-او عادی خواهیم داشت برای مثال ??۱۳۲۱۱۳ چنین صفحه‌ای را به ما می‌دهد. هر یک از این حالت‌ها باید یا با دایره یا با ضربدر پر شوند پس طبق اصل لانه کبوتری ۲ تا از آن‌ها باید با علامت مشابه پر شوند. از آن جهت که هر یک از این حالت‌ها قسمتی از خطوط ترکیبیاتی ما هستند، عضو سوم باید با علامت مخالف پر شود (زیرا ما فرض کردیم که هیچ‌کدام از خطوط ترکیبیاتی، ۳ عضو پر شده با علامت مشابه را ندارد). از این رو ما می‌توانیم ابر مکعب ۶ بعدی را با توجه به حالت‌های بالا به ۶ دسته تقسیم بندی کنیم.(اگر یک عضو از چند دسته پیروی کند می‌توانیم یک حالت قرار دادی در نظر بگیریم مثلاً بالاترین دسته در دسته بندی بالا). حال هفت عضو ۱۱۱۱۱۱، ۱۱۱۱۱۲ ،۱۱۱۱۲۲، ۱۱۱۲۲۲، ۱۱۲۲۲۲، ۱۲۲۲۲۲ ،۲۲۲۲۲۲ را در در نظر بگیرید. | ## بخش 3: قضیه هیلز–جووت | برای مثال فرض کنید ۱۱۱۱۱۲ و ۱۱۲۲۲۲ در یک دسته قرار بگیرند، پس ۱۱۱۱۱۲۱۱، ۱۱۱۱۱۲۲۲، ۱۱۲۲۲۲۱۱، ۱۱۲۲۲۲۲۲ دارای علامت ضربدر و ۱۱۱۱۱۲۳۳، ۱۱۲۲۲۲۳۳ دارای علامت دایره هستند. اما حال، حالت ۱۱۳۳۳۲۳۳، که باید یا با دایره یا با ضربدر پر شود را در نظر می‌گیریم اگر با ضربدر پر شود، پس خط ترکیبیاتی 11xxx2xx کاملاً با ضربدر پر می‌شود که با فرض ما در تضاد است. برعکس اگر با دایره پر شود خط ترکیبیاتی کاملاً با دایره پر شده‌است که دو باره با فرض ما در تضاد است. این وضعیت برای هر یک از دو عضو از هفت عضو بالا از که در یک دسته مشابه قرار گیرند مشابه است. از آن جهت که ما برای همه دسته‌ها تضاد داریم، پس فرض اولیه ما غلط بوده، پس باید حداقل یک خط ترکیبیاتی وجود داشته باشد که کاملاً از دایره یا ضربدر تشکیل شده باشد. اگر کسی بحث بالا را برای مقادیر عمومی و گسترش دهد، به سرعت رشد خواهد کرد، حتی زمانی که است (که به ۲ بازیکن بازی ایکس او بر می‌گردد) ای که از روابط بالا محاسبه شود حتی سریع تر از تابع اکرمن رشد خواهد کرد. است، که با استفاده از توابع اصلی بازگشتی به دست آمد، و همچنان، در حالت کلی، بهترین کران برای عدد هالس-جووت، می‌باشد. ارتباط با دیگر قضایا دقت کنید که استدلال بالا نتیجهٔ روبه رو را نیز می‌دهد :اگر فرض کنیم که مجموعه تمام اعداد ۸ رقمی با ارقام ۱٬۲،۳ باشد،(برای مثال A شامل ۱۱۳۳۳۲۳۳ نیز می‌باشد) اگر مجموعهٔ را با دو رنگ، رنگ کنیم، دنباله‌ای حسابی به طول ۳ وجود دارد که همهٔ اعضای آن یک رنگ هستند، چرا که تمام خطوط ترکیبیاتی که در اثبات قضیه هیلز–جووت ظاهر می‌شوند، دنبالهٔ حسابی نیز هستند. با حالت کلی تر این استدلال، می‌توان نشان داد که قضیه هیلز–جووت ،قضیهٔ ون در واردن را تعمیم می‌دهد! که درقضیهٔ سمردی مطرح می‌شود، در این نسخهٔ قوی تر شده، به جای رنگ کردن ابر مکعب با رنگ، ابر مکعب و زیر مجموعه‌ای از آن به اسم با چگالی δ بین صفر و یک داده شده‌است، این قضیه می‌گوید که برای به اندازهٔ کافی بزرگ، که وابسته به وδ است، مجموعهٔ باید شامل یک خط ترکیبیاتی باشد به طوری که کل اعضای این خط در قرار دارند. | ## جمع‌بندی | شماره‌ای از مجلهٔ نیویورک تایمز که در تاریخ ۱۳ دسامبر ۲۰۰۹ منتشر شد از پروژه‌ای گزارش داد که توسط آقای تیموثی گاورز، استاد دانشگاه کمبریج و دارندهٔ مدال فیلدز، انجام شد.