k i N

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 747 razy

k i N

Post autor: mol_ksiazkowy »

Wyznaczyć najmniejsze takie \(\displaystyle{ N}\), że istnieje \(\displaystyle{ 2k+1}\) różnych liczb naturalnych o sumie większej niż \(\displaystyle{ N}\) i takich, że suma dowolnych \(\displaystyle{ k}\) z nich jest nie większa niż \(\displaystyle{ \frac{N}{2} }\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: k i N

Post autor: Premislav »

Dla ścisłości: przyjmuję, że naturalne to całkowite dodatnie.

Jeśli respektujemy coś takiego, jak suma jednej liczby ( 8-) ), to dla \(\displaystyle{ N=8}\) działa \(\displaystyle{ k=1}\) i liczby \(\displaystyle{ 2,3,4}\). Tę wersję oznaczmy przez \(\displaystyle{ A}\).
Troszeczkę ciekawiej będzie jeśli uznamy, że musi być \(\displaystyle{ k\ge 2}\); wówczas dla \(\displaystyle{ N=34}\) pasują z pewnością liczby \(\displaystyle{ 5,6,7,8,9}\) (i wtedy oczywiście \(\displaystyle{ k=2}\)). Tę wersję nazwijmy \(\displaystyle{ B}\). Pozostaje udowodnić, że nie da się zbić wartości \(\displaystyle{ N}\).

\(\displaystyle{ A)}\) W szczególności największa spośród \(\displaystyle{ 2k+1}\) liczb musi być nie większa niż \(\displaystyle{ \frac N 2}\), co dla \(\displaystyle{ N\le 7}\) daje największą z liczb nieprzekraczającą \(\displaystyle{ 3}\), a że \(\displaystyle{ 2k+1\ge 3}\), to mamy do sprawdzenia tylko układ \(\displaystyle{ 1,2,3}\), który nie spełnia tezy dla żadnego \(\displaystyle{ N}\) (sprawdzenie na palcach).

\(\displaystyle{ B)}\) Jeżeli przyjmujemy \(\displaystyle{ k\ge 2}\), to nie ma satysfakcjonującego nas układu \(\displaystyle{ 2k+1}\) liczb, gdy \(\displaystyle{ N\le 33}\). Istotnie, przypuśćmy nie wprost, że jest inaczej i oznaczmy nasze liczby przez \(\displaystyle{ a_{1}<a_{2}\ldots<a_{2k+1}}\).
Łatwo widać, że musi być \(\displaystyle{ \frac{33}{2}\ge\frac N 2\ge a_{k+2}+a_{k+3}+\ldots+a_{2k+1}\ge k a_{1}+((k+1)\ldots+2k)\\=ka_{1}+k\cdot \frac{3k+1}{2}\ge \frac{3k^2+3k}{2}}\),
czyli \(\displaystyle{ 11\ge k^2+k}\), a że \(\displaystyle{ f(k)=k^2+k}\) jest rosnąca w dodatnich i \(\displaystyle{ f(3)>11}\), więc wystarczy rozpatrzyć \(\displaystyle{ k=2}\) (wszak w tym wypadku \(\displaystyle{ k=1}\) wykluczamy). Ma więc zajść
\(\displaystyle{ a_4+a_5\le \frac N 2}\), a jednocześnie \(\displaystyle{ a_{1}+a_{2}+a_{3}+a_{4}+a_{5}>N}\). Zważywszy, że \(\displaystyle{ a_i}\) są naturalne i parami różne, mamy
\(\displaystyle{ a_{4}+a_{5}\ge 2a_1+7\ge 9}\), stąd zaś \(\displaystyle{ N\ge 18}\). Skoro \(\displaystyle{ a_1+a_2+a_3+a_4+a_5>N}\), to
\(\displaystyle{ a_1+a_2+a_3+a_4+a_5\ge N+1}\), a to w zestawieniu z \(\displaystyle{ a_4=a_5\le \frac N 2}\) daje nam
\(\displaystyle{ a_1+a_2+a_3\ge \frac N 2+1\ge 10}\). To pozwala nam na kolejną poprawę szacowania \(\displaystyle{ a_4+a_5,}\) a zatem i \(\displaystyle{ N}\):
mianowicie \(\displaystyle{ a_2+a_3\ge 8}\) (przez sprzeczność: jak nie, to \(\displaystyle{ a_2\le 3}\) i \(\displaystyle{ a_1\le 2}\), ale wtedy \(\displaystyle{ a_1+a_2+a_3\le 9<10}\)), a wobec tego \(\displaystyle{ a_4+a_5\ge a_2+2+a_3+2\ge 12}\), stąd \(\displaystyle{ \frac N2\ge 12}\) i \(\displaystyle{ N\ge 24}\).
Analogicznie jak poprzednio wykazujemy, iż \(\displaystyle{ a_1+a_2+a_3\ge 13}\), co za tym idzie, \(\displaystyle{ a_2+a_3\ge 10}\), w konsekwencji \(\displaystyle{ a_4+a_5\ge 14}\), stąd \(\displaystyle{ N\ge 28}\), znowuż \(\displaystyle{ a_1+a_2+a_3\ge \frac N2+1\ge 15}\), wobec tego \(\displaystyle{ a_2+a_3\ge 11}\), przeto \(\displaystyle{ a_4+a_5\ge 15}\), a zatem \(\displaystyle{ N\ge 30}\), więc \(\displaystyle{ a_1+a_2+a_3\ge 16}\), czyli \(\displaystyle{ a_2+a_3\ge 12}\), stąd \(\displaystyle{ a_4+a_5\ge 16}\), w konsekwencji \(\displaystyle{ N\ge 32}\) i \(\displaystyle{ a_1+a_2+a_3\ge 17}\), więc \(\displaystyle{ a_2+a_3\ge 13}\), tj. \(\displaystyle{ a_4=a_5\ge 17}\) i \(\displaystyle{ N\ge 34}\), sprzeczność (NB dowód nie wprost jest tu zupełnie zbędny, a moje rozpisywanie na pałę można by zastąpić zwięzłym algorytmem), a rozkład dla \(\displaystyle{ N=34}\) już podałem. :mrgreen:
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: k i N

Post autor: Brombal »

\(\displaystyle{ k=2}\), \(\displaystyle{ N=10}\)
\(\displaystyle{ 1+2+3+4+5=15}\)
\(\displaystyle{ 2\cdot 5 \le 10 \le 15}\)
Ostatnio zmieniony 31 sie 2021, o 18:47 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: k i N

Post autor: Jan Kraszewski »

Brombal pisze: 31 sie 2021, o 11:04 \(\displaystyle{ k=2}\), \(\displaystyle{ N=10}\)
\(\displaystyle{ 1+2+3+4+5=15}\)
\(\displaystyle{ 2\cdot 5 \le 10 \le 15}\)
Chyba nie doczytałeś treści zadania:
mol_ksiazkowy pisze: 26 sie 2021, o 09:50 i takich, że suma dowolnych \(\displaystyle{ k}\) z nich jest nie większa niż \(\displaystyle{ \frac{N}{2} }\)
A przecież \(\displaystyle{ 4+5>5=\frac{10}{2}.}\)

JK
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: k i N

Post autor: Brombal »

Jak widać nie doczytałem ;-)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: k i N

Post autor: Premislav »

Być może zadanie byłoby ciekawsze, gdyby miało taką formę, że dla ustalonego \(\displaystyle{ k\in \NN^+}\) znajdujemy najmniejsze \(\displaystyle{ N}\) o tej charakterystyce (tj. wynik jest uzależniony od \(\displaystyle{ k}\)), ale raczej za głupim na to.
ODPOWIEDZ