Κάθε 8-αδα μεταξὺ τῶν 1,2,...,30 περιέχει δύο 4-δες μὲ τὸ ἴδιο ἄθροισμα.

Γ.-Σ. Σμυρλής · #1

ΠΡΟΒΛΗΜΑ. Ὁποιαδήποτε ὀκτάδα ἀκεραίων στὸ $\{1,2,\ldots,30\}$ περιέχει δύο διαφορετικὲς τετράδες μὲ τὸ ἴδιο ἄθροισμα.

ΣΧΟΛΙΑ.

(i) Τὸ πρόβλημα τὸ βρῆκα σὲ δύο ἰστοσελίδες καὶ λογικὰ ἔχει σχετικῶς ἁπλὴ λύση, ποὺ δὲν ἔχω κατορθώσει νὰ βρῶ.

(ii) Ἔτρεξα πρόγραμμα FORTRAN καὶ πράγματι ἰσχύει τὸ ἀνωτέρω. Μάλιστα ἰσχύει κάτι ἰσχυρότερο: Ἐξακολουθεῖ νὰ ἰσχύει ἀκόμη καὶ ἂν τὸ σύνολο $\{1,2,\ldots,30\}$ ἀντικατασταθεῖ ἀπὸ τὸ σύνολο $\{1,2,\ldots,40\}$ . Παύει δὲ νὰ ἰσχύει ἀπὸ τὸ 41 καὶ μετά.

Συγκεκριμένα, στὸ $\{1,2,\ldots,41\}$ ὑπάρχουν ἀκριβῶς τέσσερεις τέτοιες ὀκτάδες:

$\displaystyle{ 1,\,2,\,3,\,11,\, 20,\, 35,\, 38,\, 41 }$
$\displaystyle{ 1,\,2,\,3,\,20,\, 29,\, 35,\, 38,\, 41 }$
$\displaystyle{ 1,\,4,\,7,\,13,\, 22,\, 39,\, 40,\, 41 }$
$\displaystyle{ 1,\,4,\,7,\,22,\, 31,\, 39,\, 40,\, 41 }$

alexandrosvets · #2

Καλησπέρα σας!
Αν δεν κάνω λάθος,οποιαδήποτε οκτάδα με 7 περιττούς και 1 άρτιο αριθμό ,δεν έχει τετράδες με ίδιο άθροισμα.
Οπότε,μήπως έχει παρερμηνευθεί κάτι;
Φιλικά,
Βέτσικας Αλέξανδρος

#3

alexandrosvets έγραψε: ↑
Πέμ Δεκ 12, 2019 6:50 pm
Καλησπέρα σας!
Αν δεν κάνω λάθος,οποιαδήποτε οκτάδα με 7 περιττούς και 1 άρτιο αριθμό ,δεν έχει τετράδες με ίδιο άθροισμα.
Οπότε,μήπως έχει παρερμηνευθεί κάτι;
Φιλικά,
Βέτσικας Αλέξανδρος

Όπως το καταλαβαίνω επιτρέπεται οι τετράδες να έχουν κάποια στοιχεία τα ίδια. Αυτό που απαγορεύεται είναι να είναι ακριβώς οι ίδιες.

$\rule{400pt}{0.5pt}$

Το γεγονός ότι ισχύει μέχρι το 40 με κάνει να πιστεύω ότι υπάρχει κάποια απλή λύση. Αυτή που βρήκα όμως δεν είναι και τόσο απλή. Γενικά το πρόβλημα σχετίζεται με τα Sidon sets και υπάρχουν καλά ασυμπτοτικά αποτελέσματα.

Πάμε λοιπόν στη λύση:

Θα γράψω $x_1 < x_2 < \cdots < x_8$ για τους ακεραίους. Υποθέτω προς άτοπο ότι δεν υπάρχουν τέτοιες τετράδες. Έχουμε συνολικά

τετράδες. Μεγαλύτερο άθροισμα είναι το x_5+x_6+x_7+x_8

και μικρότερο το x_1+x_2+x_3+x_4

. Πρέπει λοιπόν

$\displaystyle (x_8 + x_7 + x_6 + x_5) - (x_4+x_3+x_2+x_1) \geqslant 69 \quad (1)$

αλλιώς θα έχω δύο τετράδες με το ίδιο άθροισμα.

Έστω τώρα $A = \{x_1,x_2,x_3,x_4\}$ και $B = \{x_5,x_6,x_7,x_8\}$ . Μπορώ να σχηματίσω

τετράδες παίρνοντας δύο στοιχεία από το

και δύο από το

. Το μεγαλύτερο άθροισμα το έχει η τετράδα $\{x_3,x_4,x_7,x_8\}$ και το μικρότερο η τετράδα $\{x_1,x_2,x_5,x_6\}$ . Πρέπει λοιπόν

$\displaystyle (x_8+x_7+x_4+x_3) - (x_6+x_5+x_2+x_1) \geqslant 35 \quad (2)$

Κοιτάζοντας τα σύνολα $\{x_1,x_2,x_3,x_4,x_5\}$ και $\{x_6,x_7,x_8\}$ και παίρνοντας

ή

στοιχεία από το πρώτο σύνολο (

τετράδες) με παρόμοιο τρόπο παίρνω

$\displaystyle (x_8+x_7+x_5+x_4) - (x_6+x_3+x_2+x_1) \geqslant 59 \quad (3)$

Από τις (1) και (3) παίρνουμε

$\displaystyle (x_8 + x_7 + x_5) - (x_3+x_2+x_1) \geqslant 64 \quad (4)$

Όμως

$\displaystyle (x_8 + x_7) - (x_2 + x_1) = (x_8 - x_2) + (x_7-x_1) \leqslant 28 + 27 = 55 \quad (5)$

αφού αν x_8 - x_2 = x_7 - x_1

τότε

.

Από τις (4) και (5) παίρνω

$\displaystyle x_5 - x_3 \geqslant 9 \quad (6)$

Από συμμετρία παίρνω επίσης και

$\displaystyle x_6 - x_4 \geqslant 9 \quad (6')$

Οι (2) και (3) δίνουν

$\displaystyle (x_8 + x_7 + x_4) - (x_6 + x_2 + x_1) \geqslant 47 \quad (7)$

η οποία μαζί με την (5) δίνει

$\displaystyle x_6 - x_4 \leqslant 8 \quad (8)$

Από την (6) όμως έχω άτοπο.

Κάθε 8-αδα μεταξὺ τῶν 1,2,...,30 περιέχει δύο 4-δες μὲ τὸ ἴδιο ἄθροισμα.

Κάθε 8-αδα μεταξὺ τῶν 1,2,...,30 περιέχει δύο 4-δες μὲ τὸ ἴδιο ἄθροισμα.

Re: Κάθε 8-αδα μεταξὺ τῶν 1,2,...,30 περιέχει δύο 4-δες μὲ τὸ ἴδιο ἄθροισμα.

Re: Κάθε 8-αδα μεταξὺ τῶν 1,2,...,30 περιέχει δύο 4-δες μὲ τὸ ἴδιο ἄθροισμα.

Μέλη σε σύνδεση