Dana jest liczba naturalna \(\displaystyle{ n}\) oraz zbiory liczb naturalnych \(\displaystyle{ A}\), \(\displaystyle{ B}\)\(\displaystyle{ \subseteq \left[ 0,n\right]}\) takie że \(\displaystyle{ \left| A\right|+\left| B\right| \ge n+2}\). Pokaż, że istnieją takie \(\displaystyle{ a \in A}\) i \(\displaystyle{ b \in B}\) , że \(\displaystyle{ a+b}\) jest potęgą dwójki.
[Teoria liczb] Podzbiory, potęga liczby 2
: 21 sie 2011, o 00:41
autor: Damianito
Ukryta treść:
Zauważmy, że teza zadania zgodnie z lematem Halla o skojarzeniach implikuje istnienie bijekcji \(\displaystyle{ f}\) ze zbioru \(\displaystyle{ [0,...,n]}\) w niego samego o własności takiej, że dla każdego \(\displaystyle{ x}\) liczba \(\displaystyle{ f(x)+x}\) jest potęgą dwójki. Warto się zastanowić czemu tak jest, tutaj ograniczymy się do prostej obserwacji, że istnienie takiej funkcji implikuje tezę. Przy założeniach zadania bowiem zbiór \(\displaystyle{ f^{-1}(B)}\) ma \(\displaystyle{ |B|}\) elementów, czyli \(\displaystyle{ |A|+|f^{-1}(B)|\geq n+2}\) implikuje, że istnieje \(\displaystyle{ x}\) należące zarówno do \(\displaystyle{ A}\) jak i do \(\displaystyle{ f^{-1}(B)}\), czyli \(\displaystyle{ a=x\in A}\) oraz \(\displaystyle{ b=f(x)\in B}\) spełniają warunek, że \(\displaystyle{ a+b}\) jest potęgą dwójki. Pozostaje nam zatem udowodnić istnienie funkcji \(\displaystyle{ f}\), co uczynimy przez indukcję.
Dla \(\displaystyle{ n=1}\) weźmy \(\displaystyle{ f(0)=1}\), \(\displaystyle{ f(1)=0}\). Załóżmy, że istnieją odpowiednie funkcje dla \(\displaystyle{ n=1,...,k}\). Możliwe są następujące przypadki w dowodzie tezy dla \(\displaystyle{ n=k+1}\):
1) \(\displaystyle{ k+1=2^m}\) dla pewnego \(\displaystyle{ m\geq 1}\), a wtedy weźmy funkcję \(\displaystyle{ f(x)=(k+1)-x}\)
2) \(\displaystyle{ k+1=2^m+s}\) dla pewnych \(\displaystyle{ m \geq 1}\) oraz \(\displaystyle{ s}\) z \(\displaystyle{ 0<s<2^m-1}\). Wtedy ustalamy \(\displaystyle{ f(x)=2^{m+1}-x}\) dla \(\displaystyle{ x=2^m-s,2^m-s+1,...,2^m+s}\) A dla \(\displaystyle{ x=0,...,2^m-s-1}\) bierzemy \(\displaystyle{ f(x)=f_1(x)}\), gdzie \(\displaystyle{ f_1}\) jest istniejącą ze względu na założenie indukcyjne odpowiednią funkcją dla \(\displaystyle{ n=2^m-s-1}\)
3) \(\displaystyle{ k+1=2^m+s}\) dla pewnego \(\displaystyle{ m \geq 1}\) i \(\displaystyle{ s=2^m-1}\), tj. \(\displaystyle{ k+1=2^{m+1}-1}\). Wtedy defniujemy \(\displaystyle{ f(x)=2^{m+1}-x}\) dla \(\displaystyle{ x \neq 2^m}\) i \(\displaystyle{ x\neq 0}\), a poza tym \(\displaystyle{ f(0)=2^m}\) i \(\displaystyle{ f(2^m)=0}\)
Otrzymujemy zatem, że istnieje żądana funkcja dla \(\displaystyle{ n=k+1}\), co kończy dowód kroku indukcyjnego, czyli też tezy zadania. Można zauważyć, że dowiedliśmy nawet, że istnieją funkcje spełniające nasze warunki spełniające w dodatku zależność \(\displaystyle{ f(f(x))=x}\).