sprawdzenie czy dany ciag jest permutacja

miko03 · Post autor: **miko03** » 30 mar 2013, o 14:59

Witam,jest to moj pierwszy post wiec prosze o wyrozumialosc
ostatnio na uczelni dostalismy zadanie dla chetnych z matematyki dyskretnej takiej tresci:
nalezy udowodnic ze jezeli mamy pewny zbior liczb ,nalezy udowodnic ze wszystkie permutacje tego zbiory maja te wlasnosc ze suma ich wartosci jest rowna sumie tego zbiory i iloczyn tak samo mianowicie iloczyn wszystkich elementow permutacji jest rowny iloczynowi wszystkich elementow zbioru,trzeba pokazac ze jezeli biore sobie jakas permutacje tego zbioru i zmieniam dowolna liczbe elementow tak by ich suma pozostala ta sama to iloczyn sie zmieni:
potrafie to prosto pokazac jezeli zmieniamy wartosci tylko 2 elementow ale nie wiem jak zrobic przejscie indukcyjne
potrafie to udowodnic ale kozystajac z tego ze:
(a+n1)(b+n2)*...*(z+nn)<abc*...*z(n1+n2+n3+...+nn)
a tego jakosc nie moge udowodnic

Errichto · Post autor: **Errichto** » 30 mar 2013, o 16:12

To co w końcu trzeba pokazać? Że dowolna permutacja zbioru ma sumę elementów równą sumie elementów początkowego zbioru (i to samo z iloczynem)? Bo "trzeba pokazac ze jezeli biore sobie jakas permutacje tego zbioru i zmieniam dowolna liczbe elementow tak by ich suma pozostala ta sama to iloczyn sie zmieni" nie jest prawdą i za dużo sensu nie ma.
A co do tego, że suma elementów po permutacji się nie zmienia - bez żadnej indukcji skorzystaj z tego że dodawanie jest przemienne. Czyli kolejność dodawanych składników nie ma znaczenia. To samo z iloczynem.
A jeśli źle zrozumiałem, to musisz jaśniej się wyrazić.

yorgin · Post autor: **yorgin** » 30 mar 2013, o 16:15

trzeba pokazac ze jezeli biore sobie jakas permutacje tego zbioru i zmieniam dowolna liczbe elementow tak by ich suma pozostala ta sama to iloczyn sie zmieni:

Osobiście ciekawi mnie pogrubiona część.

Mnożenie i dodawanie jest przemienne. Koniec dowodu.

miko03 · Post autor: **miko03** » 30 mar 2013, o 16:27

np:
biore ciag 1,2,3
chce sprawdzic czy ciag a,b,cjest permutacja tejgo wczesniejszego zbioru jesli
a=1+x,b=2+y-x,c=3-y,czyli suma tych elementow pozostala ta sama ale trzeb udowodnic ze ich iloczy sie zmieni
chodzi o to zeby pokazac ze jesli mamy zbior liczb{a,b,c,d,e,f,...,n}
to jakis tam zbior jest permutacja tego wczesniejszego wtedy i tylko wtedy gdy suma jego elementow jest rowna sumie tego wczesniejszego i gdy iloczyn jego elementow jest rowny iloczynowi tego poprzedniego

yorgin · Post autor: **yorgin** » 30 mar 2013, o 16:32

Dla mnie to twierdzenie jest fałszywe.

Zbiory \(\displaystyle{ \{0,1,4\}}\) oraz \(\displaystyle{ \{0,2,3\}}\) mają takie same sumy i iloczyny, ale w sposób oczywisty jeden nie jest permutacją drugiego.

miko03 · Post autor: **miko03** » 30 mar 2013, o 16:36

wlasnie zapomnialem dodac ze zaden ze skladnikow permutacji nie moze byc rowny 0 i wszystkie elementy sa liczbami naturalnymi

Errichto · Post autor: **Errichto** » 30 mar 2013, o 16:42

Następnym razem formułuj zadanie nieco prościej. Zadanie brzmi zatem (czy może jeszcze inaczej?):
Udowodnić, że zbiór jest permutacją drugiego zbiory wtedy i tylko wtedy, gdy suma i iloczyn wszystkich elementów są takie same (+ warunki: ta sama liczba elementów, brak zer).
No to dowód:
W prawą stronę prosto - z przemienności dodawania i mnożenia.
W lewą stronę - jeśli tez zbiory mają taki sam element to wyrzucasz go z obu i dzielisz iloczyny przez wyrzuconą liczbę. Od sum odejmujesz tę samą liczbę. Równość iloczynów/sum się nie zmienia (były równe wtedy i tylko wtedy gdy będą równe). Jeśli trafisz na sytuację gdy nie ma takich samych elementów - zbiory były różne (to nie permutacje). Jeśli do końca dasz radę wyrzucać - elementy były takie same tu i tu.

Dodam, że to nie jest gotowy zapis dowodu. Podałem tylko sposób, Tobie pozostaje to zrozumieć i zapisać ładnie.

yorgin · Post autor: **yorgin** » 30 mar 2013, o 16:45

W lewą stronę - jeśli tez zbiory mają taki sam element to wyrzucasz go z obu i dzielisz iloczyny przez wyrzuconą liczbę. Od sum odejmujesz tę samą liczbę. Równość iloczynów/sum się nie zmienia (były równe wtedy i tylko wtedy gdy będą równe). Jeśli trafisz na sytuację gdy nie ma takich samych elementów - zbiory były różne (to nie permutacje). Jeśli do końca dasz radę wyrzucać - elementy były takie same tu i tu.

To rozumowanie da się sformalizować bardzo fajną indukcją, gdzie tak naprawdę wystarczy to pokazać dla zbiorów dwuelementowych.-- 30 marca 2013, 16:47 --

miko03 pisze:wlasnie zapomnialem dodac ze zaden ze skladnikow permutacji nie moze byc rowny 0 i wszystkie elementy sa liczbami naturalnymi

Grunt to poprawnie, zrozumiale, i ze wszystkimi szczegółami formułować problem...

miko03 · Post autor: **miko03** » 30 mar 2013, o 16:55

latwo jest to udowodnic gdy zmieniam tylko 2 wyraz :
mam zbior liczb a,b,c,d...z niech ich iloczy jest rowny I a suma S
biore sobie 2 wyrazy tego zbioru i zmieniam je w taki sposob
n=n+x,m=m-x w ten sposob nie zmienilem sumy calego zbioru a zebym nie zmienil iloczynu to musi byc spelniona roownosc (n+x)(m-x)=nm
nm-xn+xm-x^2=nm
-x^2+x(m-n)=0 czyli x=0 lub x=n-m
gdy x=0 to nic nie robimy permutacja zostaje bez zmian a gdy x=n-m to poprost zamieniam te liczby
ale nie wiem jak to udowodnic gdy zmieniam wiec wyrazow-- 30 mar 2013, o 16:57 --"Grunt to poprawnie, zrozumiale, i ze wszystkimi szczegółami formułować problem..."
rzeczywiscie strasznie to wszystko zagmatwalem,
"To rozumowanie da się sformalizować bardzo fajną indukcją, gdzie tak naprawdę wystarczy to pokazać dla zbiorów dwuelementowych." moglbys napisac dokladnie jak bys chcial to przedstawic czy chodzi o cos takiego jak napisalem we wczesniejszym poscie?

Errichto · Post autor: **Errichto** » 30 mar 2013, o 17:00

Podałem Ci już sposób rozwiązania... Możesz go formułować indukcją lub nie, ale po co próbujesz robić od zera? Ja się chyba poddaję w takim razie.
yorgin, nawet chyba nie trzeba pokazywać dla dwuelementowych. Ogólnie przyjemne zadanie, fajne nawet rozwiązanie ma.

miko03 · Post autor: **miko03** » 30 mar 2013, o 17:18

do tej pory mam cos takiego:
1.udowodnione gdy wybieram i zmieniam 2 liczby z ciagu
2.udowodnione dla przypadku gdy :
ciag pierowtny wyglada tak \(\displaystyle{ (a _{1}, b_{1},..., z_{1},x)}\)jego suma wynosi jakies S,a iloczyn jego wartosci jakies I
tworze drugi ciag zmieniajac iles tam elementow pierwotnego o jakies liczby czyli
\(\displaystyle{ (a _{1}+n _{1} , b_{1}+ n_{2} ,..., z_{1}+ n_{n},x )}\) gdzie \(\displaystyle{ \sum_{i=1}^{n} n _{i} =N}\),i zakladam ze iloczyn wszytskich jego elementow nie zmienil sie
teraz do ostatniego elementu odejmuje N po to by suma byla ta sama i odrazu widac ze iloczyn wtedy sie zmieni
3.pozostaje przypadek gdy po zmianie elementow czyli po utworzeniu:
\(\displaystyle{ (a _{1}+n _{1} , b_{1}+ n_{2} ,..., z_{1}+ n_{n},x )}\) iloczyn tez sie zmienil
tutaj doszedlem do czegos takiego:
niech iloczyn tego pierwotnego wynosi \(\displaystyle{ I*x}\),a suma \(\displaystyle{ S}\)
po zmianie czyli po utworzeniu
\(\displaystyle{ (a _{1}+n _{1} , b_{1}+ n_{2} ,..., z_{1}+ n_{n},x )}\) mam suma rowna \(\displaystyle{ S+N}\) a
iloczyn rowny jakies \(\displaystyle{ I_{2}}\)
teraz zmieniam ostatni wyraz tak by suma wszystkich byla tak jak w pierwotnym S czyli:
\(\displaystyle{ (a _{1}+n _{1} , b_{1}+ n_{2} ,..., z_{1}+ n_{n},x-N )}\),mam teraz ze suma jest \(\displaystyle{ S}\) a iloczy wynosi teraz \(\displaystyle{ \frac{I_{2} }{x} *(x-N)}\)
zatem musimy udowodnic ze :
\(\displaystyle{ \frac{I_{2} }{x} *(x-N)=I*x}\)
ciagnac to dalej ma rownanie kwadrtatowe postaci:
\(\displaystyle{ 0=I* x^{2}-I_{2}*x+I_{2}*N}\)
czyli delta tego trojmianu musi byc ujemna :
stad \(\displaystyle{ I^{2}_{2}<4*I*N*I_{2}}\)
czyli
\(\displaystyle{ I_{2}<4*N*I}\)
a czy to czasem nie jest zawsze spelnione?