mathematica.gr • Σύνολο που παράγει σύνολο

Σελίδα 1 από 1

Σύνολο που παράγει σύνολο

Δημοσιεύτηκε: Δευ Μαρ 18, 2013 8:40 pm

από socrates

Έστω το σύνολο $M=\{1,2,3,...,19 \}$ και $A=\{a_1,a_2,...,a_k\}\subset M .$
Να βρείτε την ελάχιστη τιμή του

, για την οποία υπάρχουν $a_i,a_j\in A$ που ικανοποιούν την ιδιότητα:
αν $b\in M,$ τότε a_i=b

a_i=b

ή $a_i\pm a_j=b.$

Re: Σύνολο που παράγει σύνολο

Δημοσιεύτηκε: Τρί Μαρ 19, 2013 1:11 am

από Παύλος Μαραγκουδάκης

socrates έγραψε:Έστω το σύνολο $M=\{1,2,3,...,19 \}$ και $A=\{a_1,a_2,...,a_k\}\subset M .$
Να βρείτε την ελάχιστη τιμή του , για την οποία υπάρχουν $a_i,a_j\in A$ που ικανοποιούν την ιδιότητα:
αν $b\in M,$ τότε ή $a_i\pm a_j=b.$

Το σύνολο $\left\{1,2,3,9,16 \right\}$ παράγει το

Θα δείξουμε ότι κανένα υποσύνολο του

με

στοιχεία δεν παράγει το

Ας υποθέσουμε ότι το $\left\{a,b,c,d \right\}$ με $1\leq a<b<c<d\leq 19$ παράγει το

Χρησιμοποιώντας τα a,b,c,d

a,b,c,d

μπορούμε να παράγουμε στοιχεία του

με

το πολύ τρόπους:
$\displaystyle{a+a,a+b,a+c,a+d,b+b,b+c,b+d,c+c,c+d,d+d,b-a,c-a,c-b,d-a,d-b,d-c,a,b,c,d}$
To άθροισμα d+d

d+d

είναι το μεγαλύτερο από αυτά και δεν μπορεί να ισούται με 19.

19.

Αναγκαστικά d+d>19

d+d>19

γιατί διαφορετικά δεν θα πιανόταν το 19.

19.

Άρα $M=\left\{\displaystyle{a+a,a+b,a+c,a+d,b+b,b+c,b+d,c+c,c+d,b-a,c-a,c-b,d-a,d-b,d-c,a,b,c,d} \right\}$
Επομένως c+d=19

c+d=19

με $d\geq 10$ και $c\leq 9.$
Προσθέτοντας βρίσκουμε 3a+5b+7c+7d=1+2+...+19=190

3a+5b+7c+7d=1+2+...+19=190

οπότε

3a+5b=57.

Αποκλείεται να είναι b=8.

b=8.

Άρα $b\leq 7$ και $a\leq 6$ οπότε $3a+5b\leq 18+35=53,$ άτοπο.
Το ελάχιστο

είναι επομένως το