רצף לנגפורד

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

בעיית לנגפורד היא המשימה של מציאת רצף לנגפורד לערך נתון (n).

היסטוריה

ק' דדלי לנגפורד התבונן בבנו המשחק בשש קוביות צבעוניות - שתיים מכל צבע. הוא הבחין שהילד סידר אותן כך שבין קוביות מצבע א' הפרידה קובייה אחת, ובין שתי קוביות מצבע ב' הפרידו שתי קוביות ובין הקוביות הנותרות הפרידו שלוש קוביות. בשנת 1958 הצליח לנגפורד להוכיח שזהו הסידור האפשרי היחיד, מלבד היפוכו. הוא בדק גם רצף של ארבעה צבעים, וגילה שגם בזה יש רק סידור אחד אפשרי.

לנגפורד מצא כי אין סידור מתאים לחמישה ושישה צבעים, אך לשבעה צבעים יש 26 סידורים אפשריים.

באופן כללי, יש פתרונות אפשריים רק למספרים שהם כפולה של 4 (n = 4k) או כפולה של 4 פחות 1 (n = 4k - 1).

מיכאל קרייצקי, כריסטוף ז'ילטואלן בי הריצו בשנת 2005 תוכנית מחשב במשך שלושה חודשים ומצאו שיש בדיוק 46,845,158,056,515,936 סידורים אפשריים של 24 זוגות צבעים.

דוגמה

לדוגמה, רצף לנגפורד עבור n = 3 ניתן על ידי הרצף: 2,3,1,2,1,3. זהו הרצף היחיד הקיים עבור n=3, מלבד היפוכו.

רצף דומה

רצף לנגפורד קשור בקשר הדוק לרצף סקולם המוגדר באותו האופן, אך הרצף הוא 0, 0, 1, 1, ..., n - 1, n - 1.

קישורים חיצוניים

• ג'ון מילר, בעיית לנגפורד, 2006.
• אריק וויינשטין, בעיית לנגפורד באתר MathWorld.
• אלגוריתם בשפת Java למציאת פתרון יחיד או מספר פתרונות.