جستجوی حقیقت ریاضی در پازل های سکه های تقلبی

مجموعه ای از پازل های اخیر دارای مقیاس توازن دو تابه فروتن، که از لحاظ تاریخی نمادی از تجارت و دولت، هنر و علم است. ترازوهای تعادل در ریاضیات تفریحی نیز محبوب هستند. معماهای تعادل نیاز به استدلال روشن و منطقی دارند و به خوبی به تعمیم ریاضی کمک می کنند. بیایید ببینیم چگونه کوانتوم خوانندگان این ویژگی ها را در پازل های زیر متعادل کردند.

پازل 1

شما هشت سکه با ظاهر یکسان دارید. یکی تقلبی و سبکتر از بقیه است که وزن آنها یکسان است. سکه بد را در دو وزن پیدا کنید. فرمول کلی حداکثر تعداد سکه هایی را که می توانید سکه های تقلبی را در آنها پیدا کنید، پیدا کنید x توزین ها

پرداختن به یک نسخه ساده از یک مشکل اغلب کلید راه حل را آشکار می کند. در این حالت تصور کنید که فقط سه سکه دارید که یکی از دو سکه سبکتر است. اگر هر یک از آنها را با یکی از دو نفر دیگر وزن کنید، یا متعادل می شوند یا نمی کنند. اگر این کار را نکنند، می دانید کدام سبک تر است. اگر تعادل برقرار کنند، سومی سبک است. شما فقط به یک وزنه نیاز دارید.

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

توجه داشته باشید که اگر در گروه بدون وزن سه عدد وجود داشته باشد، این نیز کار می کند، بنابراین می توانستیم با نه سکه شروع کنیم. با پیروی از این منطق، و با سه سکه شروع می‌کنیم، برای هر وزن اضافی می‌توانیم سکه سبک را در سه برابر تعداد سکه‌هایی که قبلا داشتیم پیدا کنیم. فرمولی که حداکثر تعداد سکه را به ما می دهد n in w توزین است بنابراین n = 3^w.

پازل 2

شما 12 سکه با ظاهر یکسان دارید. یکی از آنها سنگین‌تر یا سبک‌تر از بقیه است که وزن‌های یکسانی دارند.

1. سکه بد را در سه وزن پیدا کنید.

2. حداکثر تعداد سکه هایی که می توانید در چهار توزین برای آنها سکه بد پیدا کنید چقدر است؟ توضیح دهید که چگونه سکه جعلی را پیدا می کنید.

راه حل این معما به خوبی توسط پخش کردن، که همچنین نشان داد که در واقع می توانید سکه بد را در بین 13 سکه در سه وزن تشخیص دهید. در اینجا راه حل تد (با تورفتگی برای جدا کردن سه وزن در هر مورد):

با وزن کردن 4 سکه در مقابل 4 سکه شروع کنید.

حالت اول: در صورت عدم تعادل، برای توزین دوم، 1 عدد از طرف سنگین تر را در هر دو طرف ترازو به همراه 2 عدد از طرف سبک تر قرار دهید.

1a: در صورت نامتعادل بودن، سکه بد یا 2 سکه هنوز روی سمت سنگین است یا سکه تکی که هنوز روی سمت سبک است.

2 سکه سنگین ممکن را وزن کنید، سکه بد یا سنگین‌تر از این دو است، یا تک سکه سبک اگر متعادل هستند.

1b: اگر توزین دوم متعادل باشد، سکه بد یکی از 2 مورد استفاده نشده از سمت سبک تر توزین اول است.

آنها را با یکدیگر وزن کنید، سبک تر بد است.

مورد 2: در صورت تعادل، سکه بد یکی از 5 سکه باقی مانده است. 3 مورد از آنها را در برابر هر 3 مورد قبلاً وزن کرده (که خوب هستند) وزن کنید.

مورد 2a: اگر نامتعادل باشد، می دانید که سکه بد یکی از آن 3 است و سبک یا سنگین است.

وزن سوم هر 2 مورد از آنها در برابر یکدیگر است - اگر نامتعادل باشد، سکه بد را مشخص می کند، اگر متعادل باشد آخرین سکه از این سه است.

مورد 2b: اگر توزین دوم متعادل باشد، سکه بد یکی از 2 مورد باقی مانده است.

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

پخش کردن همچنین در ادامه نشان داد که حداکثر تعداد سکه برای چهار توزین 40 عدد است. فرمول این پازل این است: n = (3^w − 1)/2.

برای پازل‌های باقی‌مانده، فرمول‌های تعمیم‌یافته هنوز توسط ریاضی‌دانان حرفه‌ای در دست بررسی هستند و موضوع مقالات منتشر شده هستند، که برخی از آنها توسط ریاضیدانان ذکر شده است. Rainer Aus dem Spring. من به راه حل هایی برای تعداد اندک سکه هایی که در پازل ها در نظر می گیریم اکتفا می کنم و فقط به کلیاتی اشاره می کنم که به طور طبیعی از روش های مورد استفاده در این موارد ناشی می شود.

پازل 3

این یک تنوع از پازل 1 است. شما دوباره هشت سکه با ظاهر یکسان دارید که یکی از آنها سبکتر از بقیه است. با این حال، اکنون شما سه ترازو دارید. دو تا از ترازوها کار می کنند، اما سومی شکسته است و نتایج تصادفی می دهد (گاهی درست و گاهی اشتباه است). شما نمی دانید کدام ترازو شکسته است. برای یافتن سکه سبک چند وزن لازم است؟

همانطور که در مسئله 1 دیدیم، این فقط به دو وزن با تعادل خوب نیاز دارد. همچنین می دانیم که دو ترازوی خوب همیشه با هم مطابقت دارند، بنابراین اگر فقط هر وزنه را روی هر سه ترازوی تکرار کنیم، به پیشنهاد خواننده، پاسخ را در شش توزین خواهیم داشت. اگر بخواهیم این کار را در تعداد وزن های کمتر انجام دهیم، کمی مشکل می شود. ما نمی‌توانیم یک ترازو خوب را فقط با وزن کردن سکه‌های مشابه روی دو ترازو تشخیص دهیم، زیرا حتی اگر موافق باشند، ممکن است یکی از این دو ترازو بد باشد. (این همچنین نشان می دهد که اطلاعات غلط یا اطلاعات تصادفی به راحتی می تواند حقیقت را مبهم کند.)

در واقع، این مشکل، بسیار هوشمندانه، تنها در چهار وزن قابل حل است! Rainer Aus dem Spring راه حل را با استفاده از یک نماد جدید که به نظر می رسد برای این پازل ایجاد شده است، ارسال کرد. اما قبل از اینکه به آنجا بروید، می‌خواهم سناریویی را تصور کنید که امیدوارم همه چیز را شهودی‌تر کند.

تصور کنید شما کارآگاهی هستید که در حال تحقیق در مورد یک تصادف در کشوری کوچک هستید که اتومبیل های آن پلاک های دو رقمی دارند و فقط از ارقام 0، 1 و 2 استفاده می کنند. سه نفر، A، B و C، این حادثه را مشاهده کرده اند. دو نفر از آنها همیشه به یک سوال سه گزینه ای پاسخ صحیح می دهند و یکی پاسخ های کاملا تصادفی می دهد. شما نمی دانید پاسخ دهنده تصادفی کیست. شما باید از هر یک از آنها یک سوال سه گزینه ای بپرسید و سپس برای کسب اطلاعات بیشتر، کسی را که قطعا حقیقت را می گوید انتخاب کنید.

در اینجا نحوه انجام آن آمده است. از A بپرسید که آیا رقم اول 0، 1 یا 2 است. فرض کنید A می گوید 2. از B بپرسید که آیا رقم دوم 0، 1 یا 2 است. فرض کنید B می گوید 1. سپس از C بخواهید بین این سه عبارت یکی را انتخاب کند:

• فقط الف حقیقت را می گوید.
• فقط ب راست می گوید.
• هر دو حقیقت را می گویند.

شما می توانید آن چیزی را که C به شما می گوید باور کنید و از آن شخص در مورد رقم دیگر سوال کنید. برای اینکه بفهمید چرا، در نظر بگیرید که اگر A دروغ می گوید، C قابل اعتماد است و می گوید که B راست می گوید. رقم دوم در واقع 1 خواهد بود و سپس می توانید از B در مورد رقم اول سوال کنید. به طور مشابه، اگر B دروغ می گوید، C دوباره قابل اعتماد است و می گوید که A راست می گوید. سپس رقم اول در واقع 2 است و می توانید A را در مورد رقم دوم سوال کنید. در نهایت، اگر C دروغ می‌گوید، هر دو A و B قابل اعتماد هستند، بنابراین شما همچنان می‌توانید هر کسی را که C به او می‌گوید باور کنید و انتخاب کنید. (و اگر C بگوید A و B هر دو حقیقت را می گویند، پس هر دو باید درست باشند.) نکته کلیدی در اینجا این است که انتخاب سوالات شما اجازه نمی دهد C به گونه ای دروغ بگوید که در مورد A و B شک و تردید ایجاد کند. از آنجایی که حداقل یکی از A و B باید قابل اعتماد باشد، همیشه می توانید پاسخی را انتخاب کنید که C با آن موافق است، حتی اگر فقط یک پاسخ تصادفی باشد. اگر هر سه آنها موافق باشند، پس شما از قبل هر دو رقم پلاک را دارید.

در اینجا نحوه ترجمه این داستان به پازل ما آمده است. ترازوها A، B و C هستند. شما می توانید دو رقم پلاک را به سکه ها به صورت زیر ترجمه کنید: 01 سکه 1، 02 سکه 2، 10 سکه 3، 11 سکه 4، 12 سکه 5، 20 سکه 6، 21 سکه 7 و 22 سکه 8 است. خوانندگان زیرک متوجه خواهند شد که این سیستم اعداد پایه 3 (یا سه تایی) است. همچنین توجه داشته باشید که یک عدد ممکن اضافی 00 وجود دارد که می توانید از آن برای سکه نهم استفاده کنید که این تکنیک نیز مانند پازل 1 برای آن کار خواهد کرد.

برای اولین توزین، سکه ها را بر رقم اول (پایه 3) آنها تقسیم می کنید، بنابراین سه گروه شما سکه های [1، 2]، [3، 4، 5] و [6، 7، 8] خواهند بود. [3، 4، 5] را در برابر [6، 7، 8] روی ترازو A وزن کنید. اگر A به خوبی کار می کند، گروه رقم اول صحیح را مانند پازل 1 خواهید داشت. به طور مشابه، برای وزن دوم روی ترازو B گروه های شما آنهایی با رقم دوم یکسان خواهند بود: [1، 4، 7]، [2، 5، 8] و [3، 6]. اگر B به خوبی کار می کند، رقم دوم صحیح را خواهید داشت. برای وزن کشی سوم، روی ترازو C، گروهی را که A مشخص کرده است، در مقابل گروهی که B انجام می دهد، وزن می کنید. به دنبال مثال ما، برای 21، گروه ها [6، 7، 8] و [1، 4، 7] خواهند بود. سکه 7 را نمی توان همزمان روی دو طرف گذاشت، بنابراین آن را کنار گذاشته و [6، 8] و [1، 4] را با یکدیگر وزن می کنیم. توجه داشته باشید که اگر A و B هر دو قابل اعتماد باشند، در واقع 7 پاسخ صحیح است و مهم نیست که کدام طرف روی C سبکتر باشد. شما پاسخ خود را (سکه 7) تنها در سه وزن دارید. اگر A قابل اعتماد باشد و B نباشد، سکه سبکتر در [6، 8] است که مقیاس C تایید می کند و اگر B قابل اعتماد باشد و A نیست، سکه سبکتر در [1، 4] است که در کدام مقیاس C قرار دارد. نیز تایید خواهد کرد.

بنابراین در سه توزین یا سکه نور را شناسایی کرده‌ایم یا آن را به یک گروه دو نفره محدود کرده‌ایم و همچنین یک ترازو کار را شناسایی کرده‌ایم. وزن چهارم بر روی ترازو A یا B (هر ترازو C با آن موافق بود) بقیه را انجام می دهد.

این راه حل به نظر من بسیار زیباست!

این روش را می توان تعمیم داد تا لایت سکه را از بین 3 پیدا کرد^2x سکه در 3x + 1 توزین با مجموعه معین ترازو. بنابراین برای 81 سکه به هفت وزنه نیاز دارید. برای تعداد بیشتر سکه (>~1,000)، یک راه حل حتی قوی تر وجود دارد.

پازل 4

شما 16 سکه دارید که هشت تای آنها سنگین و هم وزن هستند. هشت مورد دیگر سبک و هم وزن هستند. شما نمی دانید کدام سکه سنگین است یا سبک. سکه ها یکسان به نظر می رسند به جز سکه ای که علامت های خاصی دارد. با یک ترازو خوب می توانید بفهمید که سکه مخصوص در سه توزین سبک است یا سنگین؟ حداکثر تعداد سکه هایی که می توانید با آن شروع کنید و این مشکل را در چهار وزن با موفقیت حل کنید چقدر است؟

همانطور که یکی از خوانندگان ما نتیجه گرفت، در نگاه اول، انجام این پازل در سه وزن تقریبا غیرممکن به نظر می رسد. با این وجود، با کمی هوشمندی می توان آن را انجام داد، و هر دو پخش کردن و Rainer Aus dem Spring راه حل های صحیح ارائه کرد. تد اصول کلی ارزشمندی را ارائه کرد که ارزش توجه به آنها را دارد.

اول، تا زمانی که نتیجه ای نامتعادل از وزن گیری به دست نیاوردید، اطلاعات کافی برای تعیین سنگین یا سبک بودن سکه ویژه نخواهید داشت. بنابراین باید تلاش کنید و به نتیجه نامتعادل برسید.

ثانیاً، اگر نتیجه متعادلی به دست آورید (مثلاً سکه مخصوص الف، سکه ب را متعادل می کند)، می توانید سکه هایی را که متعادل هستند ترکیب کرده و با دو سکه دیگر C و D وزن کنید. اگر نامتعادل باشند، پاسخ دارید. در غیر این صورت، اکنون تعداد سکه های مشابه را دو برابر کرده اید، که ممکن است به شما کمک کند در وزن بعدی پاسخ نامتعادل دریافت کنید. همچنین می‌توانید این فرآیند را به صورت معکوس با تعداد سکه‌هایی که توان دو (4، 8، و غیره) هستند، انجام دهید، اگر نتیجه نامتعادل اولیه دارید، همانطور که در راه حل زیر مشاهده می‌شود.

در زیر کل روشی است که می تواند نوع سکه مخصوص A را در همه موارد در سه توزین مشخص کند. (B، C و D سه سکه هستند که در همان سمت A در وزن 1 قرار می گیرند (W1)؛ X و Y دو سکه هستند که در W1 استفاده نمی شوند.)

این پازل توسط یک ریاضیدان روسی اختراع شد کنستانتین ناپ، یک مرجع جهانی در مورد پازل های توزین سکه. بسیاری از مقالات او به زبان روسی هستند، اما شما می توانید چندین پازل سکه (در میان دیگر پازل های جالب) را در وبلاگ از همکارش تانیا خووانوا.

در مورد تعمیم، آن را به شما می سپارم تا ببینید آیا همین روش برای یافتن نوع سکه خاص از بین 32 سکه که 16 سکه سنگین و 16 سکه سبک هستند کار می کند یا خیر.

پازل 5

شما باید n سکه هایی با ظاهر یکسان که برخی از آنها تقلبی و سبک تر از بقیه هستند. تنها چیزی که می دانید این است که حداقل یک سکه تقلبی وجود دارد و تعداد سکه های معمولی بیشتر از سکه های تقلبی است. وظیفه شما شناسایی تمام سکه های تقلبی است.

این واقعیت که حداقل یک سکه سبک وجود دارد و تعداد سکه های معمولی بیشتر از سکه های سبک است، این معما را حداقل برای اعداد کوچک پیچیده تر از آنچه در ابتدا به نظر می رسد، می کند. بیایید به اعداد توزین یک تا هشت سکه نگاه کنیم.

برای یک و دو سکه، در شرایط دوم هیچ سکه سبک وجود ندارد، بنابراین نیازی به توزین نیست.

سه سکه: فقط یک سکه سبک. یک وزنه برای هر پازل 1 لازم است.

چهار سکه: فقط یک سکه سبک. یک وزنه اضافی لازم است، بنابراین w = 2.

پنج سکه: یک تا دو سکه سبک. این اولین مورد جالب است. سؤال این است: آیا باید یک سکه را در برابر یک سکه سنجید یا دو سکه را در برابر دو؟

اگر یک را در برابر یک وزن کنیم، می توانیم داشته باشیم:

1. دو توزین نامتعادل: دو سکه کشف شد. ما تمام شدیم
2. یک وزن متعادل از دو: سکه های متعادل باید معمولی باشند، بنابراین آخرین سکه نیاز به وزن کردن دیگری دارد. w = 3.
3. دو توزین متعادل: در توزین سوم، یک سکه از هر توزین قبلی را با دیگری وزن کنید. اگر متعادل باشند، هر چهار تا نرمال است و سکه 5 سبک است. ما تمام شده ایم؛ w = دوباره 3. اگر نامتعادل باشند، ما دو سکه سبک را پیدا کرده‌ایم و در سه توزین تمام شده است.

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

این امر برای:

شش سکه: یک تا دو سکه سبک; w = 4.

هفت سکه: یک تا سه سکه سبک; w = 5.

هشت سکه: یک تا سه سکه سبک; w = 6. این راه حل ساختار ساده ای دارد:

• ابتدا چهار وزن یک سکه را با سکه بعدی انجام دهید. تمام سکه ها استفاده می شود.
• بدترین حالت: هر چهار توزین متعادل هستند (دو سکه سبک وجود دارد که یکدیگر را متعادل می کنند).
• دو توزین بعدی: یک سکه از وزن 1 را در برابر یک سکه از وزن 2 وزن کنید. به همین ترتیب، یک سکه از وزن 3 را در برابر سکه ای از وزن 4 وزن کنید.
• یکی از این توزین ها نامتعادل خواهد بود و دو سکه سبک را مشخص می کند. ما در شش وزن تمام شده است.

متأسفیم، دنباله ما از 0، 0، 1، 2، 3، 4، 5، 6 مطمئناً به اندازه کافی جالب نیست که بتوان به دایره المعارف آنلاین توالی اعداد صحیح!

As Jonas Tøgersen Kjellstadli اشاره کرد، به نظر می رسد راه حل است w = n − 2 برای اعداد کوچک، اما ما ثابت نکردیم که این برای اعداد بزرگتر تغییر نخواهد کرد. در برخی n، استفاده از توزین‌های چند سکه ممکن است عملکرد بهتری داشته باشد یا وزن‌های بیشتری نسبت به آن داشته باشد n − 2 ممکن است مورد نیاز باشد. ما می توانیم به سادگی راه حل هشت سکه را به تمام توان های 2 تعمیم دهیم و به آن بدهیم n − 2 به عنوان حد بالایی برای تعداد وزنه ها برای تمام توان های 2.

مارک پیرسون شباهت این مشکل را با کدهای تصحیح خطا مورد بحث قرار داد و استفاده از یک رویکرد نظریه اطلاعات را بر اساس تعداد نتایج ممکن پیشنهاد کرد. با استفاده از چنین رویکردی، مایک رابرتز یک کران پایین را برای حالت کلی تر ارسال کرد که Rainer Aus dem Spring یک تقریب برای. راینر همچنین یک پست ارسال کرد کران بالا از یک مقاله منتشر شده اما اشاره کرد که مرزها برای پایین تیز نیستند n و بنابراین برای اعداد کوچکی که در بالا در نظر گرفتیم مفید نیست. بنابراین، برای هفت سکه، کران های ذکر شده محدوده ای از 4 تا 16 را نشان می دهد که پاسخ ما، 5، بین آن قرار می گیرد. جی. پایت ارجاعات ریاضی و مرزهای اضافی برای همه پازل ها می دهد.

با تشکر از همهی افرادی که شرکت کردند. جایزه Insights برای این ماه به طور مشترک به Ted و Rainer aus dem Spring تعلق می گیرد. تبریک می گویم!

دفعه بعد می بینمت جدید مطالب مفید.