من می گم 17 سوال توضیحش واسم سخته چرا این حداقل هست ولی من یه جا خوندم سریع ترین روش برای رسیدن به یک عدد از طرف مقابل همینه : اعداد 1 تا 99999 را در مبنای دو می نویسیم که یک سری اعداد حداکثر 17 رقمی در می آید این ها را بر اساس این که رقم اول یکه یا رقم دوم یکه یا رقم سوم یکه به 17 دسته تقسیم می کنیم بعد با پرسیدن این که در کدام یک از دسته ها حضور دارد به یک عدد در مبنای دو می رسیم که این همان جواب ماست

اما در مورد حالت ب : این حالت واقعن سخته من نظر دارم اما فکر کنم کمتر از اینم راهی باشه با اضافه کردن 7 سوال می شه یه سری چیزایی را فهمید ازش می پرسیم در مبنای دو جمع 9 رقم اولش برابر اون چیزیه که ما به دست اوردیم که باعث می شود اعداد ما دو گروه شود که یا 8 تا از اعداد ما باقی می ماند یا 9 تا ما بد ترین حالت را فرض می کنیم ازش می پرسیم جمع 5 تای اول این 9 تا فلان است که باعث می شود یا 5 تا بماند یا 4 تا به همین ترتیب با پرسش 3 تای اول و دو تای اول و در نهایت می توانیم محل دقیق دروغ را در حداکثر 6 سوال پیدا کنیم بعد یک سوال دیگر که توضیح در زیر می آید

در این جا دو حالت وجود دارد یا دروغ در بخش اول مساله است یا بخش دوم اگر در بخش اول باشد که باهمان 6 سوال اخر می شود فهمید راجه به کدوم عدد دروغ گفته وگرنه ما از او یک سوال دیگر می پرسیم که آیا اون عددی که فکر می کنیم دروغ گفته اون هست یا نه اگر دروغ در بخش آخر باشه در خود هفت سوال تناقض به وجود می آید پس برای حالت ب با 17+7 یعنی 24 سوال به جواب رسیدیم

الگوریتم حریصانه
» الگوریتم های مساله های بهینه سازی معمولا مراحل مختلفی را طی می کنند ودر هر مرحله مجموعه ای از انتخاب ها پیش رو دارند برای بسیاری مسایل بهینه سازی استفاده از برنامه ریزی پویا برای تعیین بهترین اتخاب کار اضافی است میتوان با الگوریتم های ساده تر و کارا تر هم همان انتخاب را انجام داد. یک الگوریتم حریصانه همیشه گزینه ای را انتخاب می کند که در لحظه به نظر بهترین می اید .یعنی یک انتخاب محلی(نسبی)انجام می دهد به این امید که این انتخاب به یک جواب بهینه مطلق ختم شود »
مقدمه ای بر الگوریتم ها /توماس کورمن /جلد 1/صفحه ی 428
پاسخ الف:
حل از طریق الگوریتم حریصانه
با 10 سوال می توان رقم های به کار رفته را شناسایی کرد که چهار حالت زیر روی میدهد :
   1)5 رقم متفاوت داشته باشیم :
    با 1-!4 حالت می توان جای ارقام را تشخیص داد که در مجموع 33 سوال پرسیده ایم
   2)4رقم متفاوت داشته باشیم:
    یعنی یکی از رقم های ان دو بار تکرار شده با سه حرکت میتوان ان را مشخص کرد وبا12سوال میتوان جای اعداد را مشخص کرد .در مجموع با 25 سوال شماره را فهمیده ایم
   3)3رقم متفاوت داشته باشیم:
    دو حالت زیر رخ میدهد :
     1.3)دو رقم هر کدام دو بار تکرار شده:
      که با دو سوال این دو رقم تعیین شده با 4 سوال جای ارقام را می فهمیم در مجموع با17سوال شماره را فهمیده ایم
    2.3)یک رقم سه بار تکرار شده:
     با دو سوال عدد تکراری مشخص میشود حد اکثر با 8 حرکت جای اعداد مشخص شده در مجموع با 21 سوال شماره را فهمیده ایم
   4)2رقم متفاوت داشته باشیم:
    دو حالت زیر رخ میدهد :
     1.4)یکی دو بار تکرار شده ودیگری سه بار:
      با یک سوال اعداد تکراری مشخص شده وبا حد اکثر 10سوال جای ارقام مشخص میشود در    مجموع22 سوال پرسیده ایم
    2.4)یکی 4بار تکرار شده :
     در اینجا نیز با یک سوال عدد تکراری مشخص میشود با 5 سوال جای ارقام در مجموع 17 سوال
   5)1رقم متفاوت داشته باشیم:
    که با 11 سوال میتوان شماره را تشخیصداد
    پس نتیجه میگیریم که حد اقل با 33 سوال شماره را تشخیص داده ایم
لازم به ذکر است برای خلاصه شدن حل چگونگی محاسبه اورده نشده لطفا خودتان با الگوریتم حریصانه حساب کنید(اعداد اورده شده صحیح است) برای تعیین اینکه کدام یک از زیر حالت هارخ داده 1 سوال لازم است