Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Valaki mondja meg!

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]  

Szeretnél hozzászólni? Jelentkezz be.
[1503] Maga Péter2011-04-12 08:19:47

Nahát, de ostoba vagyok, ezt a Fano-síkból adódó felbontást és rokonait igazán észrevehettem volna...

Ha már az egyenes-pont felállásnál tartunk, akkor arra is mutatok egy lineáris algebrai bizonyítást (n pont, nincs mind egy egyenesen, ekkor n egyenest meghatároznak).

Először egy feladat, amit Pósa Lajos táborában tanultam. Van n pont, nincs mind egy egyenesen, mindegyikre ráírunk egy valós számot úgy, hogy minden legalább 2 pontú egyenesen 0 az összeg. Ekkor minden pontra 0-t kell írnunk. A bizonyítás nem nehéz.

Most minden Ai pontra vegyük az xi valós polinomot. Minden legalább kétpontú e egyenesre legyen P_e=\sum_{A_i\in e}x_i. Az előbb leírtak szerint a 'Pe=0 minden e-re' egyenletrendszernek csak triviális megoldása van, így legalább n egyenletből áll.

Előzmény: [1500] Zine, 2011-04-11 20:52:40
[1502] Blinki Bill2011-04-12 06:55:28

B.4351.?

Előzmény: [1498] Zine, 2011-04-09 14:09:54
[1501] Zine2011-04-11 21:52:41

még annyit, hogy viszont például a Fano-sík, mint pont-egyenes konfiguráció, az pont K7 említett felbontásának felel meg

Előzmény: [1500] Zine, 2011-04-11 20:52:40
[1500] Zine2011-04-11 20:52:40

Részben igaz a sejtés:) Két eset van, vagy az, amit te is leírsz, vagy pedig ha n = (k-1)k + 1, akkor felbontható n darab Kk-ra, például K7 felbontható 7 db háromszögre. Csak ebben a két esetben van egyenlőség.

Erdős-de Brujin-tétel a neve, ők tetszőleges pont-egyenes struktúrára fogalmazták meg, de a két megfogalmazás teljesen ekvivalens. Valamint a tétel onnan is ismerős lehet, hogy ennek egy speciális esete az az állítás, hogy n nem egy egyenesen lévő pont legalább n egyenest meghatároz. Sokszor ezt a tételt nevezik Erdős-de Brujin-tételnek az általánosabb helyett / mellett. (Persze egyből következik az is, hogy az általad sejtett eredmény ez utóbbi esetben már igaz is, mivel Gallai óta tudjuk, hogy van olyan egyenes, amely pontosan két pontot tartalmaz, vagyis a második konstrukció, amelyet említettem, a síkban nem valósítható meg, ha k legalább 2, míg gráfoknál akadálytalanul lehetséges)

Egyébként Graham-Pollak-tételt magát ismerem, de a bizonyítását nem tudom, úgyhogy majd töröm rajta én is fejem, és részemről igény biztos lesz a megoldásra, ha addig nem lesz meg. (amire elég nagy esélyt látok...)

Előzmény: [1499] Maga Péter, 2011-04-09 22:43:27
[1499] Maga Péter2011-04-09 22:43:27

Köszönöm, de a Graham-Pollak-tételé az érdem... Ha egy teljes n csúcsú gráfot felbontunk teljes páros gráfok páronként éldiszjunkt uniójára (teljes páros gráf: két színosztály, köztük minden él be van húzva), akkor legalább n-1 páros gráfot kell használnunk. Akinek van kedve hozzá, az törje rajta a fejét, hogyan lehet ezt lineáris algebrai módszerrel bebizonyítani (eléggé hasonló ahhoz, amit én írtam erre a feladatra). Ha pár napig nem lesz rá megoldás, de van érdeklődés, akkor felírom én magam. Ami ott érdekes, hogy az n-1 sokféleképp előáll.

Ebben a feladatban én az n-re másféle konstrukciót nem látok, minthogy veszünk egy teljes n-1-est, és a plusz egy pontot összekötjük mindennel. Mindazonáltal az én megoldásomból nem látszik, hogy ez lenne az egyetlen megoldás. A tiedből (ami valóban sokkal egyszerűbb) sem látom így kapásból, ami nem jelent semmit (főleg a kapásból miatt:)). Persze az sem biztos, hogy igaz.

Egyébként korábban azt írtad, hogy ez egy ismert tétel. Van esetleg neve is? (Én a kombinatorikához elképesztően nem értek, de aki ismer, az ezt tudja is. Lehet, hogy már másnak is feltűnt...:))

Előzmény: [1498] Zine, 2011-04-09 14:09:54
[1498] Zine2011-04-09 14:09:54

Ötletes megoldás:)

Egy másik általam ismert egy soros bizonyítása az állításnak: Kn = (E,V), |V| = n. Vegyünk egy v csúcsot, legyen rv azon klikkek száma, amelyek tartalmazzák. Egy L klikk csúcsainak számát, pedig jelöljük sL-lel. Tegyük fel, hogy n\geqqm. B egy olyan klikk, amelynek nem csúcsa v. Ekkor fennáll, hogy rv\geqqsB, amiből következik:

m(n-sB)\geqqm(m-rv)

1=\sum_v\sum_B\frac{1}{n(m-r_v)}\geqq\sum_B\sum_v\frac{1}{m(n-s_B)}=1

Ezzel, pedig kész is.

Előzmény: [1487] Maga Péter, 2011-04-04 20:44:45
[1497] Füge2011-04-05 19:51:28

Üdv!

Az összeg n év múlva:

a_n=a_0\left(1+\frac{p}{100}\right)^n=2a_0

Ebből \left(1+\frac{p}{100}\right)^n=2

Tehát a duplázódás független a pénzösszegtől, csak a kamattól függ.

Előzmény: [1491] KovácsPeti, 2011-04-05 16:58:53
[1496] jonas2011-04-05 19:37:16

(Sőt, lehet, hogy a 20 000 Ft egyáltalán nem duplázódik, mert a bank csak 50 000 Ft-nál nagyobb összeget enged lekötni.)

Előzmény: [1495] jonas, 2011-04-05 19:35:54
[1495] jonas2011-04-05 19:35:54

A 2 000 000 Ft duplázódik hamarabb, mert arra a bank magasabb kamatot ad.

Előzmény: [1491] KovácsPeti, 2011-04-05 16:58:53
[1494] jonas2011-04-05 19:34:32

Aha, tényleg, ez a legyegszerűbb.

Előzmény: [1492] Maga Péter, 2011-04-05 17:02:56
[1493] KovácsPeti2011-04-05 17:09:25

Javítanám előző hozzászólásom:..Évi: 8 százalék kamat, 2 különböző pénzösszeg..

Előzmény: [1491] KovácsPeti, 2011-04-05 16:58:53
[1492] Maga Péter2011-04-05 17:02:56

Alkalmazd a rendezési tételt az \left(\frac{1}{\sqrt{a}},\frac{1}{\sqrt{b}},\frac{1}{\sqrt{c}}\right), \left(\frac{1}{\sqrt{a}},\frac{1}{\sqrt{b}},\frac{1}{\sqrt{c}}\right) kollekciókra!

Előzmény: [1488] WhiteTiger94, 2011-04-05 15:55:15
[1491] KovácsPeti2011-04-05 16:58:53

Hali! Nekem 1 kamatos kamattal kapcsolatos kérdésem lenne. Adott: Évi 82 különböző pénzösszeg: 20 000 Ft ; 2 000 000 Ft A kérdés pedig az, hogy melyik pénzösszeg duplázódik meg hamarabb, ha nem változik a kamat, illetve nem történik semmiféle tranzakció, tehát csak a kamatos kamat. Próbáltam beilleszteni a képletbe, de nem sikerült :(

[1490] WhiteTiger942011-04-05 16:45:09

Köszönöm.

Előzmény: [1489] Alekszandrov, 2011-04-05 16:40:22
[1489] Alekszandrov2011-04-05 16:40:22

Szia!

A baloldalt gyöktelenítsd és hozz közös nevezőre, majd a számlálóban előálló mértani közepek helyére írd be a számtani közepeket(természetesen ekkor jön be az ismert egyenlőtlenség). Ezután vonjál össze a számlálóban, egyszerűsíts és máris a jobboldalhoz érkeztél. Ebből már az is látszik, hogy egyenlőség csak a=b=c esetén lehetséges. Üdv!

Előzmény: [1488] WhiteTiger94, 2011-04-05 15:55:15
[1488] WhiteTiger942011-04-05 15:55:15

Üdvözlet! Lenne önökhöz, hozzátok, egy kérdésem, rendezési tétel kellene hozzá ha jól sejtem, de a megoldásról nincs sejtésem, a feladatot elvileg ábraként csatolom a hozzászólásomhoz, és azt kellene megtudnom, mikor teljesül az egyenlőség, tehát, hogyha pl. a=b=c, vagy valamikor máskor?

Előre is köszönöm a segítséget.

Az ábra:

[1487] Maga Péter2011-04-04 20:44:45

Nem ismertem a tételt, de a Graham-Pollak-tétel lineáris algebrai bizonyítása megihletett:). Szóval tegyük fel, hogy az Ai klikkekre (1\leqi\leqm>1) felbontjuk a gráfot. Minden klikkhez rendeljük hozzá a P_i=\sum_{v_j\in A_i}x_j valós polinomot. Ekkor P_i^2=2\sum_{v_j,v_k\in A_i}x_jx_k+\sum_{v_j\in A_j}x_j^2. Ha most feltesszük, hogy az Ai-k uniójában minden él pontosan egyszer szerepel, akkor

\sum_{i=1}^mP_i^2=2\sum_{1\leq i<j\leq n}x_ix_j+\sum_{i=1}^m\sum_{v_j\in A_i}x_j^2=\left(\sum_{i=1}^nx_i\right)^2-\sum_{i=1}^nx_i^2+\sum_{i=1}^m\sum_{v_j\in A_i}x_j^2\geq \sum_{i=1}^nx_i^2,

ahol az utolsó egyenlőtlenség azért áll fenn, mert a felbontás nemtriviális volt, amiből világos, hogy az eredeti gráf minden csúcsa legalább két Ai-ben szerepel.

Most indirekte tegyük fel, hogy m<n. Ekkor van nem azonosan 0 megoldása a P1=...=Pm=0 egyenletrendszernek (elemi lineáris algebra). Viszont akkor erre 0\geq\sum_{i=1}^nx_i^2>0, ami ellentmondás.

Előzmény: [1486] Zine, 2011-04-04 19:16:53
[1486] Zine2011-04-04 19:16:53

a) Igen, a Ramsey-tétel általánosítható uniform-hipergráfokra. Erről elég sok anyag van neten, pl wikipedia...

b) Ez egy viszonylag híres tétel, amelyet most szándékosan nem nevezek meg: Kn gráfot ha felbontjuk m Kn-től különböző klikkre, akkor m\geqqn

Előzmény: [1484] Radián, 2011-04-04 16:56:38
[1485] jonas2011-04-04 18:13:28

A (b) elég ismerős, de nem tudom, hol lehet megtalálni a választ.

Előzmény: [1484] Radián, 2011-04-04 16:56:38
[1484] Radián2011-04-04 16:56:38

Hello!

Két kérdésem lenne az egyszerű gráfokkal kapcsolatban.

a.) Rendelkezünk-e bármiféle információval, hogy ha egy teljes gráf éleit akarjuk kiszínezgetni három színnel akkor minimum hány csúcs esetén fog egyszínű háromszöget v. négyszöget tartalmazni a gráfunk. (Van e Ramsey-számoknak valamilyen továbbfejlesztett alakja ?)

b.) Egy n csúcsú teljes gráfot felbontjuk 1-nél több ugyancsak teljes gráfra úgy hogy a kapott "kis" gráfok semelyikének se legyen közös éle. Mennyi kell legyen e "kis" gráfok minimális számossága ?

[1483] jonas2011-03-31 21:32:23

Lehet, hogy van egyszerűbb megoldás, csak én vagyok fáradt hozzá.

Előzmény: [1482] psbalint, 2011-03-31 21:28:31
[1482] psbalint2011-03-31 21:28:31

köszönöm a segítséget. triviális feladatok között volt, és miután gondoltam/ajánlották a szitára/a szitát, én még mindig azt hittem, van valami teljesen nyilvánvaló megoldás, amit nem veszek észre.

[1481] jonas2011-03-31 21:08:12

Nem, ez így hibás, mert a mazsolák eloszlkása nem ugyanaz, mint a pálcikák eloszlása. Például ha két mazsolád és két süteményed lenne, akkor 1/4 valószínűséggel menne a bal oldali süteménybe mindkét mazsola, de 1/3 valószínűséggel menne mindkét mazsola a pálcáktól balra.

Előzmény: [1479] psbalint, 2011-03-31 20:53:43
[1480] jonas2011-03-31 21:05:56

Feltételezem, hogy ezt úgy kell érteni, hogy ha a nagymama az egész tésztába rakott mazsolákat pontosan leszámolja, és biztosan ugyanannyit, n darabot rak.

Ha a tésztát tíz részre osztja, akkor minden mazsola egymástól függetlenül kerül a tíz rész valamelyikébe, és feltesszük azt is, hogy a tíz rész pontosan egyforma méretű, vagyis egyforma valószínűséggel kerülnek beléjük a mazsolák.

Most akkor ha kiválasztassz k konkrét süteményt, akkor annak a valószínűsége, hogy az összes mazsola ezekbe kerül, (k/10)n. Ebből azt hiszem, szitával következik, hogy annak a valószínűsége, hogy minden süteménybe kerül mazsola,


\sum_{0\le k\le 10} (-1)^{n-k} \binom{10}{k} (k/10)^n

Ezt átalakítod  k \binom{10}{k} =  10 \binom{9}{k-1} alapján, majd az összeget explicit alakra hozod, és innen próbáld meg te megoldani.

Előzmény: [1476] psbalint, 2011-03-31 14:24:15
[1479] psbalint2011-03-31 20:53:43

igen ez megvolt, de még mindig nem teljesen világos. lerakunk egy sorba n golyót, és lerakunk közéjük 9 pálcikát. és ahogy sorban rakosgatjuk a pálcikákat, mindig megnézzük, hogy mekkora valószínűséggel kerül olyan helyre (pl két pálcika egymás mellé), hogy az egy süteményre 0 mazsolát eredményezne. ez így megállja a helyét? most mondhatnám hogy azért csináltam golyókkal-pálcikákkal mert egy nem szakkörös gimisnek kell elmagyaráznom (egyébként így van), de igazából azért azért, mert nem tudtam kitalálni semmilyen matematikai képletes vagyis klasszikus megoldást.

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]    [79]    [80]    [81]    [82]    [83]    [84]    [85]    [86]    [87]    [88]