Σημεία από Εσθονία

[DrStrange]

Έστω ένας θετικός ακέραιος. Να βρεθούν όλοι οι θετικοί ακέραιοι , ώστε γίνεται να επιλεχθούν διαφορετικά σημεία στις πλευρές ενός τριγώνου (διαφόρων των κορυφών του) και να συνδέσουμε μερικά από αυτά με μια ευθεία, ώστε να ισχύουν οι παρακάτω συνθήκες:
Υπάρχει τουλάχιστον επιλεγμένο σημείο σε κάθε πλευρά
Για κάθε ζεύγος επιλεγμένων σημείων και που βρίσκονται σε διαφορετικές πλευρές, στην τρίτη πλευρά υπάρχουν ακριβώς επιλεγμένα σημεία συνδεδεμένα και με το και με το και ακριβώς σημεία (στην τρίτη πλευρά πάλι) που δεν συνδέονται με κανένα εκ των , .

[Demetres]

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

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

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

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

Παίρνω τώρα μια κορυφή στην και έστω ότι έχει συνδεδεμένα σημεία στην και μη συνδεδεμένα. Κάθε κορυφή στην έχει από τα συνδεδεμένα και από τα μη συνδεδεμένα. Συνολικά λοιπόν στην έχει συνδεδεμένα και άρα μη συνδεδεμένα. Δηλαδή όλες οι κορυφές τις έχουν τον ίδιο αριθμό συνδέσεων στην και ασφαλώς το ίδιο ισχύει και για άλλα ζεύγη πλευρών.

Ειδικότερα, κάθε κορυφή της πρέπει να έχει συνδέσεις στην για ένα σύνολο από συνδέσεις. Επομένως κάθε κορυφή της έχει συνδέσεις στην . Ομοίως έχει συνδέσεις στην για ένα σύνολο από συνδέσεις στις άλλες πλευρές.

Με παρόμοιο τρόπο κάθε κορυφή έχει συνδέσεις στις άλλες ακμές. Άρα κάθε κορυφή της έχει συνδέσεις στην και κάθε κορυφή της έχει συνδέσεις στην . Τότε πρέπει και άρα .

Έστω τώρα μια κορυφή στο και το σύνολο των γειτόνων της στην . Μετράμε με δύο τρόπους τις συνδέσεις μεταξύ του και της . Για κάθε κορυφή του έχουμε συνδέσεις για ένα σύνολο συνδέσεων. Για κάθε κορυφή της έχουμε συνδέσεις για ένα σύνολο συνδέσεων. Επομένως είναι .

Συνολικά λοιπόν έχουμε σημεία.

Αυτό μπορεί να γίνει ως εξής:

Στην παίρνουμε σύνολα από σημεία το κάθε ένα. Στην παίρνουμε σύνολα από σημεία το κάθε ένα. Στην παίρνουμε σύνολα από σημεία το κάθε ένα.

Συνδέουμε κάθε κορυφή των με τις κορυφές των .
Συνδέουμε κάθε κορυφή των με τις κορυφές των .
Συνδέουμε κάθε κορυφή των με τις κορυφές των .
Συνδέουμε κάθε κορυφή των με τις κορυφές των .
Συνδέουμε κάθε κορυφή των με τις κορυφές των .
Συνδέουμε κάθε κορυφή των με τις κορυφές των .

Αυτή η κατασκευή έχει τη ζητούμενη ιδιότητα αφού αν π.χ. πάρουμε μια κορυφή στο και μια στο θα υπάρχει ακριβώς ένα από τα στο οποίο έχουν κοινές κορυφές και ακριβώς ένα στο οποίο δεν έχουν καμία κοινή κορυφή.