Κανόνας Golomb: Γραμμική Αναπαράσταση Μη Αρνητικών Ακεραίων

 Ένας κανόνας Golomb είναι ένα σύνολο μη αρνητικών ακεραίων που σημειώνονται σε μία γραμμική διάταξη, ξεκινώντας από το 0, έτσι ώστε η απόσταση κάθε ζεύγους αριθμών να είναι μοναδική και διαφορετική από αυτή οποιουδήποτε άλλου ζεύγους. 

Επιπλέον, οι αποστάσεις αυτές καλύπτουν φυσικές τιμές μέχρι την τιμή που είναι μικρότερη ή ίση με τον μέγιστο αριθμό του συνόλου. Τον κανόνα αυτόν όρισε ο Αμερικανός μαθηματικός και μηχανικός Solomon W. Golomb.

Παράδειγμα Κανόνα Golomb

Στην παρακάτω εικόνα, φαίνεται ο κανόνας Golomb για το σύνολο [0, 1, 4, 6]:

Κανόνας Golomb [0,1,4,6]

Οι αποστάσεις μεταξύ των αριθμών είναι:

• 1 (μεταξύ 0 και 1)
• 3 (μεταξύ 1 και 4)
• 2 (μεταξύ 4 και 6)
• Και άλλες που φαίνονται καθαρά στην εικόνα.

Τέλειοι και Βέλτιστοι Κανόνες Golomb

Δεν απαιτείται κάθε κανόνας Golomb να καλύπτει όλες τις αποστάσεις μέχρι τον μέγιστο αριθμό. Αν όμως το κάνει, τότε ονομάζεται τέλειος κανόνας Golomb. Για παράδειγμα, τα σύνολα [0, 1] και [0, 1, 3] είναι τέλειοι κανόνες.

Ένας κανόνας Golomb ονομάζεται βέλτιστος όταν χρησιμοποιεί τον μικρότερο δυνατό αριθμό στοιχείων για να επιτύχει το μέγιστο μήκος. Τα παραπάνω παραδείγματα είναι επίσης βέλτιστοι κανόνες.

Έχει αποδειχθεί ότι δεν υπάρχει τέλειος και βέλτιστος κανόνας Golomb για περισσότερους από τέσσερις αριθμούς.

Εφαρμογή σε Αίθουσες Συνεδριάσεων

Η επόμενη εικόνα παρουσιάζει έναν κανόνα Golomb, βέλτιστο αλλά όχι τέλειο, για τιμές μέχρι το 11 ([0, 2, 7, 8, 11]), σε μια διάταξη για αίθουσες συνεδριάσεων. Σημειώνεται ότι λείπει η απόσταση που αντιστοιχεί στην τιμή 10.

Κανόνας Golomb για αίθουσες συνεδριάσεων.

Ένας άλλος βέλτιστος αλλά μη τέλειος κανόνας Golomb για τις ίδιες τιμές είναι το [0, 1, 4, 9, 11], στον οποίο λείπει η απόσταση 6.

Δυσκολίες και Πρακτική Χρήση

Η δημιουργία κανόνων Golomb είναι σχετικά εύκολη, αλλά η εύρεση του βέλτιστου κανόνα για έναν συγκεκριμένο σκοπό είναι υπολογιστικά πολύ δύσκολη. Για σύνολα με περισσότερα από 28 στοιχεία, η αναζήτηση βέλτιστων ή τέλειων κανόνων απαιτεί πολύ εκτεταμένους συνδυαστικούς υπολογισμούς.

Μια πρακτική εφαρμογή των κανόνων Golomb είναι ο σχεδιασμός κεραιών ραδιοφώνου για την αποφυγή παρεμβολών, ιδιαίτερα σε διατάξεις ραδιοτηλεσκοπίων.