EisatoponAI: Τρίγωνο Τριπλών Αθροισμάτων: Τουλάχιστον ένας άρτιος σε κάθε γραμμή

Σχηματίζουμε ένα τρίγωνο αριθμών ως εξής: κάθε όρος μιας γραμμής είναι το άθροισμα τριών όρων της αμέσως προηγούμενης γραμμής — του αριθμού ακριβώς από πάνω του και των δύο γειτόνων του (κενό θεωρείται 0). Οι πρώτες γραμμές είναι:

Να αποδείξετε ότι από την τρίτη γραμμή και έπειτα κάθε γραμμή περιέχει τουλάχιστον έναν άρτιο αριθμό. Συγκρίνετε με το τρίγωνο του Pascal.

Λύση

1) Πολυωνυμική μοντελοποίηση

Η n-οστή γραμμή δίνει τους συντελεστές του πολυωνύμου

$(1+x+x^2)^n,$

ευθυγραμμισμένους (όπως φαίνονται στο σχήμα).

Θα εργαστούμε mod 2 (δηλαδή κρατάμε μόνο το αν ένας αριθμός είναι περιττός/άρτιος).

2) Άρτιες γραμμές $n=2m$

Στο $\mathbb{F}_2$ ισχύει το “freshman’s dream”:

$(1+x+x^2)^{2m}\equiv (1+x^2+x^4)^m \pmod 2.$

Άρα όλοι οι συντελεστές των περιττών δυνάμεων του $x$ μηδενίζονται.
Συνεπώς η γραμμή για κάθε άρτιο $n\ge 2$ περιέχει τουλάχιστον έναν άρτιο όρο. ✔️

3) Περιττές γραμμές $n\ge 3$

Περίπτωση $n\equiv 3 \pmod 4$ :
Ο συντελεστής του $x^2$ είναι
$[x^{2}] (1 + x + x^{2})^{n} = (\binom{n}{2}) + (\binom{n}{1}) = \frac{n (n - 1)}{2} + n = \frac{n (n + 1)}{2},$
που είναι άρτιος (γιατί $n$ περιττός ⇒ $(n+1)/2$ άρτιος). Άρα υπάρχει άρτιος όρος.
Περίπτωση $n\equiv 1 \pmod 4$ :
Ο συντελεστής του $x^4$ είναι
$[x^4](1+x+x^2)^n=\binom{n}{4} +n\binom{n-1}{2}+\binom{n}{2}.$
Για $n=4k+1$ καθένας από τους τρεις όρους είναι άρτιος (εύκολος έλεγχος), άρα κι αυτός ο συντελεστής είναι άρτιος.

Συμπέρασμα: Για κάθε $n\ge 2$ (δηλ. από την 3η γραμμή και κάτω) υπάρχει τουλάχιστον ένας άρτιος όρος. Οι δύο πρώτες γραμμές είναι $1$ και $1,1,1$ (όλες περιττές), όπως απαιτείται. ■

Σύγκριση με τρίγωνο του Pascal

Στο τρίγωνο του Pascal (συντελεστές του $(1+x)^n$ ) υπάρχουν άπειρες γραμμές όλες περιττές, συγκεκριμένα όταν $n$ είναι δύναμη του 2 (Θεώρημα του Lucas).
Στο παρόν τρίγωνο $(1+x+x^2)^n$ , από το $n=2$ και μετά πάντα εμφανίζεται τουλάχιστον ένας άρτιος όρος — δεν υπάρχουν «ολόκληρες περιττές» γραμμές.