🔢 Πρόβλημα Langford – Μπορείς να βρεις τη σωστή διάταξη;

Δίνεται το πολυσύνολο των αριθμών:

{1,1,2,2,3,3,…,n,n}

Μπορούμε να το διατάξουμε σε μία ακολουθία έτσι ώστε για κάθε αριθμό $k$, να υπάρχουν ακριβώς $k$ άλλοι αριθμοί ανάμεσα στις δύο εμφανίσεις του;

---

📌 Ορισμός:

Ο όρος πολυσύνολο (multiset) σημαίνει ότι επιτρέπεται να εμφανίζεται το ίδιο στοιχείο περισσότερες από μία φορές.

Στην περίπτωσή μας, κάθε αριθμός από το 1 έως το n εμφανίζεται δύο φορές.

Αυτό διαφέρει από ένα «κανονικό» σύνολο, όπου κάθε στοιχείο εμφανίζεται μόνο μία φορά.

---

✅ Παράδειγμα (n = 3)

Το πολυσύνολο είναι:

{1,1,2,2,3,3}

Μια έγκυρη διάταξη είναι:

2, 3, 1, 2, 1, 3

🔎 Ας το ελέγξουμε:

• Οι δύο άσσοι έχουν 1 αριθμό ανάμεσά τους.

• Οι δύο δυάδες έχουν 2 αριθμούς ανάμεσά τους.

• Οι δύο τριάρες έχουν 3 αριθμούς ανάμεσά τους.

👉 Η συνθήκη ικανοποιείται πλήρως.

---

ℹ️ Πότε έχει λύση το πρόβλημα;

Ο Langford απέδειξε ότι λύση υπάρχει μόνο όταν:

$$n \equiv 0 \ \text{ή} \ n \equiv 3 \pmod{4}$$

Δηλαδή, όταν το $n$ αφήνει υπόλοιπο 0 ή 3 στη διαίρεση με το 4.

---

📍 Παραδείγματα:

✅ Υπάρχουν λύσεις για:
$n = 3, 4, 7, 8, 11, 12, \dots$

❌ Δεν υπάρχουν λύσεις για:
$n = 1, 2, 5, 6, 9, 10, \dots$