کاردهای آشپزخانه ی فیبوناتچی

سکه های تقلبی

12 سکه داریم که یکی از آنها تقلبی است(معلوم نیست سنگین تر از بقیه است یا سبکتر) چگونه میتوانیم با سه بار وزن کردن اون سکه تقلبی رو پیدا کنیم؟

جواب:

12 سکه را به 3 دسته 4 تایی تقسیم می کنیم و با انتخاب 2 دسته تا از آنها توزین اول را انجام می دهیم 2 حالت پیش می آید:

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

ب) 2 دسته نا برابرند: یکی از 2 دسته حاوی سکه تقلبی است و مساله قدری سخت تراز حالت الف می شود . با خارج کردن 3 سکه از یک دسته و جابجایی 2 سکه از دسته دیگر به این دسته و افزودن 1 سکه معمولی به دسته دیگر توزین دوم را بین 2 دسته 3 تایی ایجاد شده انجام می دهیم .3 حالت پیش می آید:

ب-1) دو دسته برابرند

پس سکه تقلبی در بین 3 تای خارج شده است. با توجه به اینکه میدانیم از کدام دسته این 3 تا برداشته شده اند نوع نابرابری ان دسته در توزین اول سبکتر یا سنگینتر بودن سکه را معلوم می کند پس با توزین سوم سکه تقلبی بین این 3 سکه معلوم می شود. یعنی 2 تارا با هم می سنجیم اگر برابر بودند سومی تقلبی است واگرنابرابربودند همانی که نوع نابرابری را داشته باشد تقلبی است.

ب-2) دو دسته نابرابری خلاف توزین اول دارند پس سکه تقلبی بین 2 سکه جابجا شده است که با توزین سوم معلوم میشود.

ب-3) دو دسته نابرابری مشابه توزین اول دارند. پس سکه های خارج شده وسکه های جابجا شده (*) سکه های معمولی هستند و سکه تقلبی بین آنهایی است که جابجا نشده اند. در کل از 8 سکه مشکوک 5 تا کنار میرود و 3 سکه مشکوک باقی میماند. از دسته ای که 2 سکه دارد یکی را خارج می کنیم و1 سکه را به دسته دیگر منتقل می کنیم و در سمت دیگر 2 سکه معمولی می گذاریم توزین سوم را بین این 4 سکه انجام می دهیم .2 حالت پیش می آید:

ب-3-1) دو دسته برابرند پس سکه تقلبی سکه خارج شده است .

ب-3-2) دو دسته نابرابری خلاف توزین اول دارند پس سکه جابجا شده همان سکه تقلبی است.

ب-3-3) دو دسته نابرابری مشابه توزین اول دارند. پس سکه های خارج شده وجابجا شده سکه های معمولی هستند و سکه غیر این دو تقلبی است.