פורטל:מתמטיקה/חידה/70

עם כתיבת הערך ה-50,000 בוויקיפדיה העברית החל ישי, קורא נלהב, לקרוא אותה מתחילתה, בסדר אלפביתי של הערכים (לפי רשימת כל הערכים). ישי קורא 30 ערכים מדי יום, ומדי יום נוספים לוויקיפדיה 30 ערכים חדשים, בהתפלגות אחידה על פני כל רשימת הערכים. כמה ערכים יהיו בוויקיפדיה העברית כאשר ישי יסיים את קריאתה?

פתרון

במבט ראשון נוצר הרושם שישי לא יסיים לעולם את קריאת האנציקלופדיה, שהרי הוא קורא 30 ערכים ביום ובמקביל מתוספים 30 ערכים חדשים, כך שמספר הערכים שישי לא קרא נותר ללא שינוי. רושם זה מוטעה, מפני שככל שישי מתקדם בקריאת האנציקלופדיה (ואין ספק שהוא מתקדם, 30 ערכים מדי יום), יתחילו להתוסף ערכים חדשים גם בחלק שכבר קרא, וערכים אלה לא יפריעו להתקרבותו לסוף האנציקלופדיה. התקרבותו לסוף תהיה איטית מאוד בהתחלה, אך ככל שחולף הזמן היא תהפוך למהירה יותר.

כיוון שלא הוצג פתרון אנליטי לחידה זו, פתרתי אותה בשיטת מונטה קרלו, באמצעות סימולציה בתוכנית JavaScript קטנה:

function readwiki()
{
  var total;        // מספר הערכים הכולל
  var current=0;    // מקומו הנוכחי של הקורא
  var newarticle;   // מקומו של הערך החדש

  for (total=50000; current < total ; total++)
        {		
  	 newarticle=Math.floor(Math.random()*(total+1));
	 if (newarticle <= current)
	     {current++}   // הערך החדש נוסף לפני הערך שבו נמצא הקורא
         current++          
        }
          
  alert (total)            // הצג את מספר הערכים בסיום קריאת האנציקלופדיה
}

התוצאה: כאשר ישי יסיים את קריאת ויקיפדיה העברית, יהיו בה כ-136,000 ערכים (כיוון שמעורבת כאן אקראיות, במיקומו של ערך חדש יחסית למיקומו של ישי, לא ניתן לנקוב במספר מדויק, אך הרצות אחדות של התוכנית מגלות שהתוצאות הן סביב 136,000 ערכים).

לקבלת פתרון אנליטי נעבור מגרסה בדידה של החידה לגרסה רציפה שלה: חילזון זוחל על גומייה אידיאלית שיכולה להימתח עד אינסוף, ובאותו זמן סוס הקשור לקצה הגומייה שאליו זוחל החילזון מתקדם ומותח את הגומייה. כמה זמן ייקח לחילזון, אם בכלל, להגיע לקצה השני?
תשובה: נסמן ב- $\ V$ את קצב הזחילה, וב- $\ U$ את קצב הארכת הגומייה. לאחר זמן $t$ נוסף אורך של $U\times t$ לאורך המקורי L. לכן האורך הוא: $l(t)=L+U\times t$ .

אם החילזון נמצא במרחק $\ x$ מתחילת הגומייה הרי החלק ה- $x/l$ מהתוספת $\ U$ יהיה מאחוריו, לכן בכל רגע הוא מתרחק מההתחלה במהירות $V+U\times x/l$ זוהי המהירות האמיתית של החילזון. ואז: $dx/dt=V+U\times x/l$ או: $dx/dt=V+U\times x/(L+U\times t)$ .

נסמן $T=L/U$ ונקבל את המשוואה: $dx/dt=V+x/(t+T)$ שפתרונה (באמצעות וולפרם אלפא) הוא: $x(t)=V\times (T+t)\times ln(t+T)+c1\times (t+T)$ כאשר $\ c1$ הוא קבוע. מתוך התנאי $x(0)=0$ נקבל ש: $c1=-V\times ln(T)$ ומכאן $x(t)=V\times (T+t)\times ln(t+T)-V\times ln(T)\times (t+T)$ .

נציב $x=l$ ונקבל שהחילזון יסיים את המסלול לאחר זמן: $t=e^{(U/V)}\times (L/V)-L/U$ .

במקרה שלנו $U=V=30$ , מה שנותן לנו זמן של $(e-1)\times 50000/30$ . נכפיל בקצב התוספת ונוסיף את האורך המקורי ונקבל: $l=50000\times e$ . זה בערך $135,914$ .