دانش‌آموز بي‌حوصله‌اي در سالني كه در آن كمدهاي دربسته‌اي با شماره‌هاي 1 تا 1024 در يك رديف قرار گرفته‌اند قدم مي‌زند. او در كمد شماره 1 را باز مي‌كند و سپس در كمدها را يكي در ميان باز مي‌كند. پس از اينكه به انتهاي سالن رسيد، بر مي‌گردد. به اولين كمد در بسته‌اي كه برسد در آن را باز مي‌كند و سپس در كمدها را يكي در ميان باز مي‌كند. اين دانش‌آموز آنقدر مي‌رود و مي‌آيد كه در همه كمدها باز شود. شماره آخرين كمدي كه او درش را باز كرده است چيست؟

(آزمون دعوتي رياضيات آمريكا، 1996)

فرض كنيد  كمد در يك رديف قرار گرفته باشند و  شماره‌ي آخرين كمدي باشد كه دربش باز مي‌شود. وقتي كه دانش‌اموز براي اولين بار برمي‌گردد  كمد در بسته باقي‌مانده است. شماره‌ي همه‌ي اين كمدهاي دربسته زوج است و از جايي كه دانش‌اموز ايستاده است به‌ترتيب نزولي قرار گرفته‌اند.

اكنون از آخر، جايي كه دانش‌آموز ايستاده است، كمدهاي بسته را دوباره از 1 تا  شماره‌گذاري كنيد. توجه كنيد كه در ابتدا شماره‌اش n بوده است (كه در اين‌جا  n عددي زوج است). اكنون شماره‌اش  است. چون  شماره‌ي آخرين كمدي است كه در شماره‌گذاري جديد دربش باز مي‌شود لذا:

(رابطه‌‌ي 1)

پس:

 

 

(رابطه‌‌ي 2)

اگر از اين رابطه‌ي بازگشتي يك‌بار ديگر استفاده كنيم رابطه‌ي ذيل به‌دست مي‌آيد:

 

                   

 

(رابطه‌‌ي 3)

وقتي تعداد كمدها 1024 يا  است آخرين كمدي كه دربش باز مي‌شود  خواهد بود. چون ، اگر از رابطه‌ي 3 چند بار استفاده كنيم معلوم مي‌شود كه:
 

جواب 2

رابطه‌ي بازگشتي 3 را - كه مي‌توان آن را به‌شكل ذيل نوشت - حل مي‌كنيم:

(رابطه‌ي 4)

چون و پس داريم:


اگر  k عددي زوج باشد




اگر  k عددي فرد باشد

(رابطه‌ي 5)

اين دستورها را مي‌توان يك‌جا به‌شكل ذيل هم نوشت:






(رابطه‌ي 6)

به‌ويژه اين‌كه:




(رابطه‌ي 7)

سؤالي ديگر

به‌نظر شما اگر 1000 كمد در سالن باشد راه‌حل چه تغييري مي‌كند؟