Matematyka.pl

Wyznaczyć podzbiór Sidona (Sidon set) zbioru \(\displaystyle{ \{1,...,30 \}}\) maksymalnej mocy. Ile jest takich podzbiorów

A nie mogłeś od razu dodać definicji zbioru Sidona?

JK

Nie mógł bo nie znał...

Sidon set to taki zbiór, którego suma dwóch jego elementów jest zawsze różna od pozostałych sum nawet jak są dwa jednakowe składniki...

Np:

\(\displaystyle{ \left\{ 1,2\right\} }\)

\(\displaystyle{ 1+1=2, 1+2=3,2+2=4}\)

Jak widać, każdy zbiór dwuelementowy to Sidon set...

\(\displaystyle{ \left\{ 1,2,3\right\} }\)

\(\displaystyle{ 2+2=1+3}\) it's not Sidon set...

\(\displaystyle{ \left\{ 1,2,4\right\} }\) - Sidon set of course...

W tym zbiorze: \(\displaystyle{ [30]}\) naliczyłem, że maksymalny Sidon set ma \(\displaystyle{ 6}\) elementów, np:

coś takiego:

\(\displaystyle{ \left\{ 1,2,4,8,13,21\right\} }\)

\(\displaystyle{ \left\{ 1,3,4,8,16,22\right\} }\)

\(\displaystyle{ \left\{ 1,5,6,8,14,25\right\} }\)

.........................................................

itd...