iniektywność wektora plecakowego

[niebieska_biedronka]

Nie wiem, czy to dobry dział, ale nie bardzo wiem, gdzie założyć taki temat...

Należy pokazać, że wektor plecakowy \(\displaystyle{ (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)}\) jest iniektywny, tzn. że nie istnieje liczba naturalna \(\displaystyle{ \alpha}\) taka, że problem plecakowy \(\displaystyle{ (A, \alpha)}\) ma więcej niż jedno rozwiązanie.

Iniektywne są na pewno wektory superrosnące - ale taki? jak to pokazać?

[Zordon]

Co to znaczy problem plecakowy \(\displaystyle{ (A,\alpha)}\)?

[niebieska_biedronka]

Rozwiązanie problemu \(\displaystyle{ (A, \alpha)}\) polega na wybraniu takiego podzbioru ciągu liczb \(\displaystyle{ A}\), że jego suma wynosi \(\displaystyle{ \alpha}\). Wynikiem jest wektor złożony z zer i jedynek, tże jedynki są na tych miejscach wektora \(\displaystyle{ A}\), które są składnikami sumy.
Czyli np. rozwiązaniem problemu \(\displaystyle{ (A, 602)}\) jest wektor \(\displaystyle{ (0,1,0,1,0,0,0,0,0,0)}\), bo \(\displaystyle{ 602=129+473}\).

[Zordon]

Wskazówka: patrzeć modulo 43. Najpierw rozważyć 5 ostatnich osobno.

[niebieska_biedronka]

No okej, pięć pierwszych wyrazów to wielokrotności \(\displaystyle{ 43}\), kolejne mają jakieś tam reszty z dzielenia. I te reszty tworzą wektor superrosnący.
I co dalej?

[Zordon]

Nie wprost zakładamy, że można jakiś wynik uzyskać na dwa sposoby.
Z tego co napisałaś wynika, że nie możemy używać w tych przedstawieniach żadnej z 5 ostatnich liczb, bo wtedy nie zgodzi się reszta mod 43... To można nieco uściślić, ale myślę, że wiadomo o co chodzi.
No więc, musi być tak, że wektor złożony z pierwszych pięciu liczb nie jest iniektywny, no ale on też jest superrosnący, sprzeczność.

[niebieska_biedronka]

Dziękuję!