Ezesetben minden vektorhoz tartozik egy lekepezes 1 dimenziora (egy lepes). Mivel az egy dimenzio jol rendezett ezert ha ugyanazt a vektort hasznaltuk az origobol es vegtelenszer vegigutottuk az egyenesunket akkor lecsaptuk a bolhat.
Ismeteljuk meg ezt minden lehetseges lepessel (vektorral).
Mert ez esetben Cantor tetel alapjan Aleph nulla az n-ediken szamossaga megegyezik Aleph nullaval, azaz van az 1dimenzios ternek mappingje n dimenziora.
Ezekutan annyi a dolgunk, hogy az 1 dimenziot vegigutjuk.
Ha F-et ugy definialjuk hogy minden e (0<=e<n) dimenziot az e-dik primszamhoz kotunk es a koordinatak pedig a hatvanykitevok, akkor van egy konstruktiv megoldasunk es meg AC sem kell hozza.
Minden sorban a baloldali 3 szám: az ismeretlen x1, x2, x3 együtthatói a1, a2, a3
a1x1+a2x2+a3x3=
3 sor 3 egyenlet, tehát
a11x1+a12x2+a13x3=
a21x1+a22x2+a23x3=
a31x1+a32x2+a33x3=
A jobb oldalon is van 3 sorban 3 szám dij
Összesen 9 egyenleted van:
a11x1+a12x2+a13x3=d11
a21x1+a22x2+a23x3=d21
a31x1+a32x2+a33x3=d31
a11x1+a12x2+a13x3=d12
a21x1+a22x2+a23x3=d22
a31x1+a32x2+a33x3=d32
a11x1+a12x2+a13x3=d13
a21x1+a22x2+a23x3=d23
a31x1+a32x2+a33x3=d33
Ami tulajdonképpen:
a11x1+a12x2+a13x3=d11 ill. d12 ill. d13
a21x1+a22x2+a23x3=d21 ill. d22 ill. d23
a31x1+a32x2+a33x3=d31 ill. d32 ill. d33
Látható bal oldalon az invertálandó mátrix, jobb oldalon pedig az egységmátrix van, d11=d22=d3371, a többi d=0
Ez három egyenletrendszer, azonos baloldallal, különböző jobb oldalakkal.
Mind a 3 egyenletrendszert egyformán oldod meg, azaz bal oldal egyforma átalakításaival, amit úgy tehetsz, hogy a jobb oldalon is ugyanúgy szorzol és összeadsz-kivonsz, mint a bal oldalon.
(Szabad egy egyxenletet számmal szorozni, és szabad egy egyenletrendszeren belül két sort összeadni vagy kivonni.)
Úgy kell a fenti műveleteket (a korábban leíyrt lépésekkel) alkalmazni, hogy az az átalakítások utáni bal oldal az egységmátrix legyen.
Ismered az egyenlő együtthatók módszerét? Ez annak továbbgondolása sok ismeretlenre.
Koszonom szepen! Ezek szerint ha peldaul a bal oldali matrix masodik sorabol az elso sorat kivonom, akkor a jobb oldali matrix masodik sorabol nem a bal oldali matrix elso sorat kell kivonni, hanem a ekkor a jobboldali matrix elso sorat? Vagyis a matriixok egyik sorabol csak a sajat soraik valahogyanszorosat vonhatjuk ki?
Sehogy sem jött ki nem a Gauss eliminációval a mátrixok inverze! :(
Néztem az általunk viszgált mátrix esetét. Mellé írtam az egységmátrixot.
2 4 6 1 0 0
2 6 9 0 1 0
3 7 11 0 0 1
a bal oldali mátrix második sorából kivontam az első sorát, és a jobboldali egységmátrix második sorából kivontam a baloldali mátrix első sorát
2 4 6 1 0 0
0 2 3 -2 -5 -9
3 7 11 0 0 1
kivontam a harmadik sorból az első sor 3/2-szeresét:
2 4 6 1 0 0
0 2 3 -2 -5 -9
0 1 2 -3 -6 -8
kivontam a harmadik sorból az első sor 1/2-szeresét:
2 4 6 1 0 0
0 2 3 -2 -5 -9
0 0 1/2 -3 -7 -19/2
kivontam az első sorból a második sor kétszeresét:
2 0 0 1 -4 -6
0 2 3 -2 -5 -9
0 0 1/2 -3 -7 -19/2
kivontam az első sorból a harmadik sor hatszorosát
2 0 0 1 -4 -6
0 2 0 -2 -5 -12
0 0 1/2 -3 -7 -19/2
a sok transzformáció után a bal oldali mátrixunk diagonális lett, a jobb oldalon az egységmátrixból megkaptunk egy olyan mátrix-szal, ami a mátrixunk inverze lesz, ha az első sort elosztjuk 2-vel, a másodikat is 2-vel elosztjuk és a harmadikat 1/2-el osztjuk el.
ezek szerint az inverz mátrix
1/2 -2 -3
-1 -5/2 -6
-6 -14 -19
de ezt a mátrixot összeszorzam az eredeti mátrixunkkal:
2 4 6
2 6 9
3 7 11
akkor nem egységmátrixot kapok. Mit ronthattam el a Gauss elimináció során?
"Nekem ez a feladat jobban tetszik, mint a végtelenes."
A véges eset szerepelt valamely gyakorlaton egyetemen elsőévben (csak k-féle sapkaszínnel), arra viszonylag hamar rájöttem, számomra ez a végtelen törpés volt izgalmasabb, azt a gimis tudásommal nem is tudtam volna megcsinálni.
Nekem annó az nem volt világos, hogy nem csalás-e, hogy a törpéknek "ilyen jó" a memóriája, de aztán láttam, hogy anélkül esélytelen.
Amúgy jogos amit mondasz, nem elég pontosan fogalmaztam meg a példát. Cerébe mondok egy hasonlóan szórakoztatót:
Az n dimenziós térben van egy (potszerű) láthatatlan bolha, aki nagyon bosszant minket. A bolha valmely egész koordinátájú ponton tanyázik és van egy titkos egész koordinátájú vektora, aminek megfelelően minden pillanatban továbbugrik. Minden pillanatban miután továbbugrott van lehetőségünk ütni egyet valahova. Dolgozzunk ki módszert, amivel biztosan leütjük.
Az utolsó rab megmondja az előtte lévő 99 rab "összegét", ebből a 99. már ki tudja sakkozni, hogy mi van rajta, ezt (is) felhasználva már a 98. is meg tudja mondani és így tovább. (Azaz legalább 99 rab megmenthető.)
Ez szép és izgalmas téma, de egy idő után az ember megszokja, hogy a végtelen már csak ilyen, produkálja a meghökkentő dolgokat, de ezeknek a meghökkkentő dolgoknak végül nem nagyon lesz kihatása a véges életünkre.
Azért ez nem ilyen egyszerű. A matematika nem véletlenül olyan, amilyen. A valós vagy komplex számokat pl. nem véletlenül használjuk, akár véges (kipróbálható) állítások bizonyítására is. Pl. analízis nélkül nem tudnám bizonyítani az alábbi állítást.
Állítás. Ha p>163 egy prím, ami 8-cal osztva 3 maradékot ad, akkor a p=x2+y2+z2 egyenletnek van legalább 48 egész megoldása.
P.S. Ez nem egy ártalmatlan állítás: Gauss sejtette 200 évvel ezelőtt, és 150 évet kellett várni a bizonyításra.
Van egy függvény, ami minden sapkaleosztáshoz egy másik sapkaleosztást rendel úgy, hogy:
(1) a hozzárendelt leosztás mindig csak véges sok helyen tér el a kiindulási leosztástól
(2) ha két leosztás csak véges sok helyen tér el egymástól, akkor a függvény ugyanazt a leosztást rendeli hozzájuk
A törpék "megegyeznek" egy ilyen függvényben és aztán mindegyikük alkalmazza a függvényt arra a leosztásra amit lát (a nem látott sapkák színét tetszőlegesnek képzelve). (2) miatt minden törpe ugyanazt a "tippelt leosztást" kapja ezen a módon, nevezetesen a tényleges leosztáshoz rendelt leosztást, (1) miatt pedig ez a "tipp" csak véges sok helyen tér el a tényleges leosztástól.
Az (1)-(2) tulajdonságokat a kiválasztási axióma biztosítja. Az összes leosztás halmazát felbontjuk páronként diszjunkt nemüres részekre: egy részbe azok a leosztások tartoznak, amik egy adott leosztástól csak véges sok helyen térnek el. Ezek után minden részhez hozzárendeljük annak egy elemét, ez a keresett függvény.
Nekem ez a feladat jobban tetszik, mint a végtelenes. Leírom, hogy miért.
A végtelennel kapcsolatban én is, mint mindenki rácsodálkoztam, hogy mennyire másképp működik, mint amit a hétköznapi intuíció diktálna. Ez szép és izgalmas téma, de egy idő után az ember megszokja, hogy a végtelen már csak ilyen, produkálja a meghökkentő dolgokat, de ezeknek a meghökkkentő dolgoknak végül nem nagyon lesz kihatása a véges életünkre.
A véges kalapos feladat megoldása viszont az első hétköznapi intuíció számára úgy meghökkentő, hogy nincs semmi végtelen benne, olyan konkrét kísérletről van szó, amit a való életben is elvégezhetnénk.
A kevesebb néha több elven, kissé eltávoldott az ízlésem a végtelentől a véges felé.
Én ilyen kalapos feladatot ismertem, ebben semmi végtelen nincs, ezért teljesen gyakorlatias, hétköznapi feladatnak tekintehető:
Van 100 rab.
Ezeket egymás mögé fogják állítani sorban, és mindegyik fejére tesznek egy fekete vagy fehér sapkát. Senki nem látja a saját és a mögötte lévő rabok sapkáját, de látja az összes előttelévő sapkáját.
A rabokat hátulról kezdve egyesével meg fogják kérdezni a saját sapkájuk színéről. Aki eltalálja, azt életben hagyják, aki nem találja el, azt kivégzik.
A rabok nagyon okosak, ezért mielőtt kiviszik őket, akármilyen startégiát mondhatsz nekik, ami szerint a sapkájuk színét tippelik majd. Keressünk olyan stratégiát, amellyek a lehető legtöbb rab életemegnethető. Természetesen miután kivitték a rabokat, nem kommunikálhatnak, ami információt kapnak az csak az előtte lévők sapkaszíne, és a mögöttelévők esetén hallják a tippeket.
Tetszik ez a törpés feladat! (Van esélyem arra, hogy megértsem a megoldást? :-)) (Egyszer régen találkoztam már egy más jellegű "kalapos" feladattal. Abban egy kör alakú vár tornyaiban voltak őrök és egyszerre sétálgatni kezdtek (azonos sebességgel), s ha két őr találkozott, visszafordultak. Azt kellett bizonyítani, hogyha 1 óra alatt körbe sétálható a vár, akkor 12 óra múlva minden őr ott van, ahol kezdetben volt.)
Ohh hát ilyen törpés feladaton nem haszontalan gondolkozni.
Itt egy véges, de több dimenziós változat.
(Ez a feladat valóságos modellen alapul.)
A kiválasztási függvény és az ekvivalencia osztályokra gyakorló példa állítólag.
Ebben ez lenne a lényeges. Azokat konstruktívan felépíteni. Hogyan kell kiszámolni
egy ilyet? Nekem ez lenne érdekes benne.
(A törpék nem tudják, hogy rajtuk milyen színű és hány db sapka van. Nem is lényeges a feladat szempontjából. Nem arra kell tippeniük.)
17 törpe között felosztanak N különböző színű sapkákat, az alábbiak szerint: A 17. törpe (amit a mögötte álló 16 lát) megkapja a mögötte álló 16 törpe összes színű sapkáját és még k17 db másik színüt. A 16.törpe (aki a 17. törpe mögött áll) tehát ismeri N=N17 értékét. Az 16. törpe sapkái amit a mögötte álló 15 lát N16 különböző színűt kap. A 15. törpe is látja az előtte álló 16. és 17. törpe összes sapkáját. és így tovább. Az első törpe 0, 1 vagy 2 sapkát kap.
Legyen N=33. A rendezök felírnak k különböző színt. (Ezek szerepelnek az N17 színek között.) Továbbá megmondják a rendezők a törpéknek, hogy hány szín van a kiválasztott 8 közül a törpénél, éés az előtte álló törpénknél. N17 tehát k=8 at ismeri, de nem sokra megy vele. 1. Adjon meg kiválasztási függvényt. 2. A 16. törpe megtippeli, a 8 színt, a 15. is. Stb. 3.Lássa be, hogy a feladat dinamikus, determinisztikus. 4.Mekkora a valószínűséggel talál el az első törpe 0, 1,2,...,8 színt az általa mondott 8 színből? 5.mekkora a pi,j valószínűséggel talál el az i edik törpe j színt? i=2,..,17, J=0,1,....,8 6. Nem mondják meg a törpéknek, hogy a kiválasztott színből mennyi van nála és a kiválasztott színek számáról csak annyit, hogy nagyobb, mint 6. Adjuk meg ugyanezen valószínűségeket j=6 ra i=1 től 17.
2. bizonyítsd be, hogy [k(k+1)(k+2)]/3 + (k+1)(k+2) = [(k+1)(k+2)(k+3)]/3
A második ennek a továbbfejlesztése: néhány konkrét példa alapján tippeld meg a képletet, ellenőrizd néhány további értékre, és ha jó, akkor bizonyítsd a helyességét teljes indukcióval.
Először azt gondoltam, hogy a 3. feladatra adott megoldásod hibás, de inkább a feladat szövege pontatlan egy kicsit, mert a "sorbaállítják őket" és a "Mindenki csak az előtte lévőkét látja" mondatokat én úgy értelmeztem, hogy mindenki csak véges sokat lát. Ebben az esetben reménytelennek éreztem a feladatot. A megoldásod azt feltételezi, hogy mindenki csak véges sokat nem lát. Ezt én inkább úgy fogalmaznám, hogy mindenki csak az utána állókat látja.
Sziasztok! Tudna valaki segíteni az alábbi feladatok megoldásában? a. Bizonyítsuk be, hogy 1*2+2*3+...+n(n+1)=[n(n+1)(n+2)]/3 b. Szám ki a következő összeget: 1*2*3+2*3*4+...+n(n+1)(n+2) Köszönöm előre is!
Magasabb dimenziós mátrixok determinánsának kiszámítására is lehet ugyanezt alkalmazni?
Persze, és ugyanúgy. Mint mondtam, a matematikai szoftverek is ezt használják.
Hallottam, hogy a Gauss-eliminációs módszerrel ki lehet számítani a mátrix inverzét.
A mátrix inverzét is Gauss-eliminációval érdemes számolni. Valahogy így:
(1) Leteszed egymás mellé az eredeti mátrixot és az identitásmátrixot. Nevezzük ezeket a továbbiakban bal és jobb mátrixnak.
(2) A bal mátrixon elemi sorműveleteket (amiket a 7761-ben leírtam) alkalmazol úgy, hogy felső háromszögmátrix legyen belőle. Ugyanezeket a műveleteket sorra a jobb mátrixon is végezd el.
(3) Ezután ha a bal mátrix átlójában van nulla, akkor az eredeti mátrix nem invertálható, mert a determinánsa (ami az átlós elemek szorzata) nulla. Ha az átlóban csak nemnulla elemek vannak, akkor elemi sorműveletekkel az átló feletti elemeket is kinullázhatod, magyarán átlósmátrixot tudsz kapni a bal oldalon. A jobb mátrixon továbbra is elvégzed az összes műveletet ugyanabban a sorrendben.
(4) A bal átlós mátrix elemei most már mind nemnullák, mondjuk c1, c2, ..., cn. A jobb mátrix első sorát oszd c1-gyel, második sorát c2-vel stb.: a kapott mátrix az inverz.
A bizonyítás egyszerűbb, mint az algoritmus.
Egyébként javaslom, hogy tanuld meg rendesen a lineáris algebrát, anélkül nehéz bármit csinálni a tudományban.
"Javaslom, hogy a jövőben jelezd, ha nyitott kérdést teszel fel"
Rendben.
Jelen esetben nem tudtam, hogy nyitott kérdés-e valamelyik, csak nekem nem ment, attól még lehetett volna okosabbaknak könnyű.
A gráfos példám irányítatlan esetben NP-nehéz, G3C következne belőle (tanárom igazolta).
Amúgy ha jól látom a linkeden egy általánosítása van annak amit én mondtam, és ott nem követeli meg a férfi-nő alternálást. Wikipedián meglett az eredeti kérdésre is a válasz.
Ezért nem lepett meg, hogy hamar rátaláltam (visszaemlékeztem?) az alábbi megoldásra. Nevezzünk két sapka-leosztást ekvivalensnek, ha csak véges sok helyen különböznek. Ez egy ekvivalencia-reláció.
Igen, ez erre a sztenderd megoldás, legalábbis én is ezt ismertem; ez a Fréchet-filter. Nyilván, semmiképpen sem lehet rekurzív, vagy akár konstruktív függvénnyel definiálni a reprezentánst.
Akik ezt a feladatot nézik, sokszor, tévesen, azt gondolják, hogy algoritmust adhatnak, ha létezik megoldás. Ezért ez jó példa a nemkonstruktivitás szemléletésére.
Felmerült egyszer a kérdés, hogy ha minden valóshalmaz Lebesgue-mérhető, akkor azért konzisztens-e az AC ebben a konkrét esetben? Erre a választ nem tudom, de az illető (kutató) evidensnek vette, hogy nem.
(Érdekes, hogy a csak filterek szerinti ekvivalencia osztályokkal vett ún. redukált szorzatok milyen formulákat őriznek meg, és melyeket nem, ellentétben azzal, ha ultrafilter szerint veszünk ekvivalencia-osztályt, és ultraszorzatot használunk.)
