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: Érdekes matekfeladatok

  [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]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]  

Szeretnél hozzászólni? Jelentkezz be.
[3739] aaaa2013-06-12 18:16:21

1.a) \binom{13}{6} b) \binom{7}{3}\binom{6}{3}

2. Legyen adott a következő p permutáció: (0123)(456789) Ekkor p(x) legyen p x számjegyeire egyenként alkalmazva. Ekkor p(x) egyértelmű, x pároshoz páratlant rendel, 400000-nél nem kisebbhez 400000-nél nem kisebbet, ismétlődédes számhoz ismétlődéseset. De így ismétlődéses páros és páratlan számból ugyanannyi van a 400000-nél nem kisebbek között. Vagyis megfelelő számból \frac{10^7-4*10^6-6*9*8*7*6*5}{2}-1 van, mert 400000 is megfelelő lenne.

Előzmény: [3738] uborkalekvar, 2013-06-12 17:19:31
[3738] uborkalekvar2013-06-12 17:19:31

Sziasztok!

Valaki tudna segíteni ebben a 2 feladatban?

1. a.Hányféleképpen juthatunk el a koordináta-rendszerben az origóból a (7,6) pontba, ha egy lépés során csak jobbra, illetve felfelé léphetünk 1 egységet? b.Hány esetben haladunk át a (3,4) ponton?

2.Hány olyan valódi hatjegyű páros szám van, amely nagyobb 400000-nél és van benne ismétlődő számjegy?

Köszönöm előre is a segítséget!

[3737] aaaa2013-06-11 19:02:07

valóban igazad van, butaság, amit írtam. Újra nekifutva: Tegyük be a hálót egy koordinátarendszerbe, (0;0) legyen az egyik csúcs, egység hosszú oldala legyen a négyzeteknek, legyen a rács tengelypárhuzamos n*n-es háló, ahol n>5, az (x,y), (x,y+1) szakaszt jelölje (x,y+0.5) s (x,y), (x+1,y)-t (x+0.5,y). Az L-betűt a 2 szakasz 3 végpontjával adjuk meg, a négyzetet meg (x+0.5,y+0.5) alakban.

Na most nézzük a (0;0) sarkot. Ha L-betű van itt, akkor az (2,0)-(0,0)-(0,2), mert különben (0,0)-(0,2)-(2,2)-t és (0,0)-(2,0)-(2,2)-t használjuk, de ekkor (1,0.5) és (0.5,1) nem fedhető le átfedés nélkül. Így leraktuk a (2,0)-(0,0)-(0-2) L-betűt. Ekkor (1,0.5) és (0.5,1) csak egyféleképp fedhetők, (1,0)-(1,2)-(3,2)-vel és (0,1)-(2,1)-(2,3)-al. Ezután (2,0.5) és (0.5,2) csak (2.5,0.5)-el és (0.5,2.5)-el fedhető. Ezután (0,3.5) és (3.5,0) fedéséhez kell (0,3)-(0,5)-(2,5) és (3,0)-(5,0)-(5,2). Most ha ránézünk (4,0.5), (0.5,4)-re, akkor muszáj (4,0)-(4,2)-(6,2)-t és (0,4)-(2,4)-(2,6)-t lerakni, de ekkor (1,3.5) és (3.5,1) nem fedhető semmivel.

Konklúzió: a sarokban négyzet van, ha legalább 6*6-os négyzetről van szó, vagyis (0.5,0.5)-t fel kell használni. De ekkor (0,1.5)-t és (1.5,0)-t csak (0,1)-(0,3)-(2,3) és (1,0)-(3,0)-(3,2) fedheti, és ettől fogva (0,2n+1.5)-t és (2n+1.5,0)-t csak (0,2n+1)-(0,2n+3)-(2,2n+3) és (2n+1,0)-(2n+3,0)-(2n+3,2) fedheti.

Összefoglalva: egy legalább 6*6-os négyzet jó lefedésénél minden sarokban négyzet van, és a határszakaszokat egyértelműen fedik az L-betűk. De ekkor 2 eset van: ha n=2k+1, akkor lesz egy szakasz minden határon, amit nem tudunk lefedni, ha n=2k, akkor meg a négyzetektől induló L-betűk egymást fogják fedni, ahol a két sarokhoz tartozó L-betűk találkoznak.

A kimaradó kérdések: n=2,3,4,5-re van-e lefedés

n=2-re trivi, hogy nincs

n=3-ra (0.5,2.5), (2.5,0.5), (2.5,2.5), (2,0)-(0,0)-(0,2), (1,0)-(1,2)-(3,2) és (0,1)-(2,1)-(2,3) jó fedés

n=4-re L-betűs sarkos érvelés megakad (0,3.5) és (3.5,0)-nál, a négyzetes igaz rá, nincs fedés

n=5-re L-betűs sarkos érvelés megakad (4,0.5) és (0.5,4)-nél, a négyzetes igaz rá, nincs fedés

Összefoglalva: csak és kizárólag n=3-ra rakható ki.

Előzmény: [3736] w, 2013-06-10 22:22:03
[3736] w2013-06-10 22:22:03

Nagyon vázlatos. "A másik 2 oldal ekkor nem fedhető le egyszerre ezekkel a típusú darabokkal átfedés nélkül." Átfedés alatt azt értem, hogy két darabnak közös szakasza van. Metszhetik még egymást. (Nem tudom, erre gondoltál-e.)

Előzmény: [3734] aaaa, 2013-06-10 00:08:48
[3735] jonas2013-06-10 09:55:57

Négyzet alakú drótdarabokkal nyilván nem lehet, mert ezek a rács szélét nem tudják lefedni. Azt nem tudom, hogy L alakú darabokkal mi a helyzet.

Előzmény: [3733] w, 2013-06-06 09:21:45
[3734] aaaa2013-06-10 00:08:48

Nem, L-betűt nem használhatunk a kirakáshoz, ugyanis tekintsük az L-betű "csúcsánál" lévő négyzetet, amelynek 2 oldala az L-betűbe esik. A másik 2 oldal ekkor nem fedhető le egyszerre ezekkel a típusú darabokkal átfedés nélkül. Csak négyzetekkel meg nem lehet lefedni. (megj. ez minimum 2*2-es négyzethálóra is igazolja, hogy nem lehet)

Előzmény: [3733] w, 2013-06-06 09:21:45
[3733] w2013-06-06 09:21:45

Aha értem. Akkor témát váltok: ki lehet-e rakni egy 8x8-as négyzetrácsot átfedés nélkül a szimmetrikus, négy egységszakaszból álló L-alakú, illetve négyzet alakú drótdarabkákkal?

Előzmény: [3732] aaaa, 2013-06-06 08:31:09
[3732] aaaa2013-06-06 08:31:09

azt a megoldást ismerem máshonnét, és épp ezért nem azt írtam le, meg most már ez a becsléssorozat egy kicsit kézenfekvőbb volt :)

Előzmény: [3731] w, 2013-06-06 08:21:32
[3731] w2013-06-06 08:21:32

Lehet tanulságossá tenni. Kezdd azzal, hogy a feladatot megpróbálod szépen megoldani. Van igen szép, integrálos egyenlőtlenség nélküli megoldása, csak ahhoz gondolkodni is kell :-) Segítség: mi indukciót akarunk csinálni, csak n-re nem sikerül. Azt igazold, hogy g(n)<3.

Előzmény: [3730] aaaa, 2013-06-05 22:45:26
[3730] aaaa2013-06-05 22:45:26

Utóbbi alsó korlátja triviálisan a \sqrt{2}, felsőre meg logaritmálunk, szóval a következőt kéne minél jobban becsülni:

g(n)=exp\bigg(\sum_{i=2}^{n}\frac{\log i}{2^{i-1}}\bigg)

Mivel 2log x<x-1, ha x>4, ezért mehet a következő felső becslés: g(n)<exp\bigg(\sum_{i=2}^{n}\frac{\log i}{2^{i-1}}\bigg)=\sqrt{2\sqrt{3}}exp(\sum_{i=4}^n\frac{i}{2^i}-\frac{1}{2^i})<\sqrt{2e\sqrt3}

Ha meg nem becsülünk így felülről, hanem integrállal becsülgetünk, akkor n=10-től indítva az integrált felső korlátnak 2.76676 adódik pl, de ez nem túl tanulságos.

Előzmény: [3729] w, 2013-06-05 21:33:20
[3729] w2013-06-05 21:33:20

További algebrai ügyeskedés (ami nagyon tetszik) ennek a topicnak az első hozzászólásaiban található: mennyi lesz az

S=\sum_{k=2}^\infty \left(\zeta(k)-1\right)

összeg, ha \zeta(k) a híres Riemann-féle zéta-függvény. Riasztóbb, mint amilyen.

Új feladat következik. Egy másik függvényt mondok, pl. g-t, ami ezúttal a pozitív egészek közül a 2-nél nagyobbakra hat, és nem más, mint

g(n)=\sqrt{2\sqrt{3\sqrt{\dots\sqrt{(n-1)\sqrt n}}}}

lesz. Most nem puccoskodok, csak kérem, hogy mutassuk meg, hogy g felülről és alulról korlátos. Adjunk meg minél jobb korlátot.

Előzmény: [3728] aaaa, 2013-06-05 21:22:05
[3728] aaaa2013-06-05 21:22:05

Hú, tényleg, pozitívakra gondoltam. Igen, bernoulliból szépen kijön, vagy még a b) feladat szorzatának felső becsülgetéséből is pont ez adódik.

Előzmény: [3727] w, 2013-06-05 21:12:46
[3727] w2013-06-05 21:12:46

Aranyos. Nekem pozitív egészekre van megoldásom, de nem is baj, mert csak poz. egészekre értelmezhetők a kifejezések, vagy teljesül az egyenlőtlenség. (Utóbbi magyarázata: ha n=1 és m<0, akkor a bal oldal 1-1/(-m), a jobb oldal 1+0, ami ellentmondás.) A Bernoulli-egyenlőtlenség szerint

\left(1+\frac{1+\log n}{mn}\right)^n>1+n\cdot \frac{1+\log n}{mn}=1+\frac1m+\frac{\log n}m>1+\frac{\log n}m

és ebből n-edik gyököt vonva megkapjuk a kívántat.

Már aki nem ismeri a Bernoullit, az kínos helyzetben van, mert vagy eszébe jut a súlyozott hatványközepek közötti egyenlőtlenség (ami bizonyítja a Bernoullit), vagy (nagyobb eséllyel) rájön, hogy itt indukciót lehetne csinálni. Ennek ellenére a feladat legkönnyebb megoldása a binomiális tétellel történik (megint ekvivalens átal. n-edikre hatványozok):

\left(1+\frac{1+\log n}{mn}\right)^n=\sum_{k=0}^n \binom n k\cdot\left(\frac{1+\log n}{mn}\right)^k\ge \binom n 0+\binom n 1\cdot\frac{1+\log n}{mn}=1+\frac{1+\log n}m>1+\frac{\log n}m

Előzmény: [3726] aaaa, 2013-06-05 20:02:28
[3726] aaaa2013-06-05 20:02:28

Bizbe, hogy:

1+\frac{1+\log n}{mn}>\root{n}\of{1+\frac{\log{n}}{m}}

minden egész n és m párra.

[3725] aaaa2013-06-05 19:53:28

Remélem azért nem írtam el sehol, de:

a) Legyen:

P_{l,n}=\prod_{i=l}^n\frac{3i+2}{3i+1},
\qquad Q_{l,n}=\prod_{i=l+1}^n\frac{3i}{3i-1}, \qquad R_{l,n}=\prod_{i=l+1}^n\frac{3i+1}{3i}

Ekkor Ql,n+1>Pl,n>Rl,n>Ql,n, ez pl. tényezőnkénti összehasonlítással adódik, az alsó ill felső becsléshez használt PQR típusú két szorzat meg teleszkópos, lesz. Ekkor

\frac{3l+3}{3n+1}=P_{l,n}Q_{l,n+1}R_{l,n}>P_{l,n}^3>P_{l,n}Q_{l,n}R_{l,n}=\frac{3l+2}{3n+1}

\root3\of{\frac{3l+3}{3n+1}}>P_{l,n}>\root3\of{\frac{3l+2}{3n+1}}

A feladatban l=2666, n=333, így \root{3}\of{8,001}>P>2 adódott.

b) Először is, ha xi>0 teljesül a következő, egyenlőség i=1 esetén:

\prod_{i=1}^n (1+x_i)\geq 1+\sum_{i=1}^n x_i

Vagyis, felhasználva \sum_{i=1}^n i^{-1}>\log n-et:

\prod_{i=1}^n \Big(1+\frac{1}{mi}\Big)\geq 1+\frac{1}{m}\sum_{i=1}^n\frac{1}{i}>1+\frac{\log (n)}{m}

Szóval minden m>0-ra tart a végtelenbe.

Előzmény: [3724] w, 2013-06-05 15:27:35
[3724] w2013-06-05 15:27:35

Definiáljuk a pozitív egész számokon értelmezett f(n,m) függvényt a következőképpen:

f(n,m)=\prod_{k=1}^n \frac{mk+1}{mk}.

(a) Nagyobb vagy kisebb a

P=\frac{8000}{7999}\cdot\frac{7997}{7996}\cdot\frac{7994}{7993}\cdot\dots\cdot\frac{1004}{1003}\cdot\frac{1001}{1000}

kifejezés a kettőnél?

(b) Mely m számok esetén lesz \lim_{n\to\infty} f(n,m)=\infty?

[3723] w2013-05-29 21:56:44

Nagyon köszönöm!

Előzmény: [3722] m2mm, 2013-05-29 21:25:04
[3722] m2mm2013-05-29 21:25:04

Legyen A={1,2,...,n}. Ekkor az A-> A szürjektív leképezések száma n! ugye. Másfelől ha azon leképezések halmaza Ai, melyek képének nem eleme i, akkor a logikai szita szerint |A_1\cup A_2\cup...\cup A_n|=-\sum_{k=1}^n (-1)^k\binom{n}{k} (n-k)^n. Másfelől |A1\cupA2\cup...\cupAn|=nn-n!. Szóval n^n-n!=-\sum_{k=1}^n (-1)^k\binom{n}{k} (n-k)^n, n!=n^n+\sum_{k=1}^n (-1)^k\binom{n}{k} (n-k)^n=\sum_{k=0}^{n}(-1)^k\binom{n}{k} (n-k)^n.

n!=\sum_{k=0}^{n}(-1)^k\binom{n}{k} (n-k)^n=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{n-k}k^n=\sum_{k=1}^{n}(-1)^{n-k}\binom{n}{k}k^n.

Előzmény: [3720] w, 2013-05-26 19:26:07
[3721] w2013-05-26 19:31:50

Ennek mintájára igazoljuk, hogy

\sum_{k=0}^n (-1)^{n+k} \binom n k k^{n+1}=\frac n2 \cdot n!

[3720] w2013-05-26 19:26:07

Visszatérve Lajos problémájára, helyettesítsünk be A=0, h=1-et, és vegyük az f(x)=xn polinomot!

\sum_{k=1}^n (-1)^{n-k}\binom n k k^n=n!

Ilyen formára írtam át korábban az összegét, ami tehát valóban 1-gyel egyenlő.

Amúgy ez elvileg ismert azonosság volna, úgyhogy egy kombinatorikai megoldást szívesen megnéznék.

Előzmény: [3719] w, 2013-05-26 19:17:40
[3719] w2013-05-26 19:17:40

Olvasgatás közben rábukkantam a következő azonosságra:

\sum_{k=0}^n (-1)^{n-k} \binom nk f(A+kh) = a_n\cdot h^n\cdot n!

ahol f(x)=anxn+an-1xn-1+...+a1x+a0, f\inR[x] polinom, h\neq0, A valós számok, n pozitív egész.

Vajon hogyan igazolnánk?

Nemrég merült fel a következő segédfeladat. Keressük meg az összes legfeljebb n-edfokú p polinomot, amelyre adott páronként különböző a0, a1, ..., an és x0, x1, ..., xn számok mellett p(xi)=ai (\foralli=0,1,...n)!

Megoldás. Először megbecsüljük, hány ilyen polinom lehet. Tegyük fel, hogy két különbözőt is találtunk. Ekkor a két polinom különbsége (n+1) db helyen (x0, x1, ..., xn helyeken) nulla, bár legfeljebb n-edfokú, azaz csakis a zéruspolinom lehet, ami ellentmond annak, hogy különböző polinomokat vettünk. Idő kérdése, amíg konstruálunk is egyet:

p(x)=\sum_{i=0}^n a_i\cdot\prod_{0\le j\neq i\le n} \frac{x-x_j}{x_i-x_j}

xi behelyettesítés után láthatóan jó lesz.

Ezt hívják a Lagrange-féle interpolációs polinomnak (amit gondolom a hozzászólók nagy része ismer).

Megoldás. Vegyük az f(x) legfeljebb n-edfokú függvényre felírt interpolációs képletet:

f(x)=\sum_{k=0}^n f(A+kh)\cdot\prod_{j\neq k} \frac{x-(A+jh)}{(k-j)h}

. Ezután nézzük meg a két oldalon álló polinomok főegyütthatóját!

a_n=\sum_{k=0}^n f(A+kh)\cdot1/\bigg(\prod_{j\neq k}\big((k-j)h\big)\bigg)

(Ugyanis az int. azonosságban minden egyes k-ra megnézve a tagot, a számlálóban lévő szorzat elvégzése után csak egy darab xn keletkezik.)

Az utóbbi kifejezés tovább alakítható:

a_n=\sum_{k=0}^n f(A+kh)\cdot1/\bigg(\prod_{j\neq k}\big((k-j)h\big)\bigg)=

=\sum_{k=0}^n f(A+kh)\cdot \frac1{h^n\cdot k(k-1)(k-2)\cdot\dots\cdot1\cdot(-1)\cdot\dots\cdot(k-n)}=

=\sum_{k=0}^n f(A+kh)\cdot (-1)^{n-k} \cdot \frac{n!}{k!\cdot(n-k)!}:(n!\cdot h^n)

a_n\cdot n!\cdot h^n=\sum_{k=0}^n f(A+kh)\cdot (-1)^{n-k} \cdot \binom n k

Készen vagyunk.

Előzmény: [3717] Lóczi Lajos, 2013-04-22 01:41:38
[3718] w2013-04-30 16:59:56

Az összeget jobban szeretem a következő alakban:

\frac1{n!} \cdot \sum_{k=0}^n (-1)^{n+k} k^n \binom n k=1.

(Direkt odaírtam, hogy az összeg valójában 1-gyel egyenlő. Ja meg itt n:=p, mert p általában prímet jelöl, továbbá az m betű futó indexben, kombinatorikai azonosságban nem tetszik nekem. Számomra ilyen formában sokkal áttekinthetőbb, de nem szeretnék erről vitát kezdeni.)

Előzmény: [3717] Lóczi Lajos, 2013-04-22 01:41:38
[3717] Lóczi Lajos2013-04-22 01:41:38

Legyen p pozitív egész. Mennyi ekkor \sum_{m=1}^p \frac{(-1)^{m+p}m^{p-1}}{(m-1)!(p-m)!} értéke?

[3716] gyula602013-04-19 21:35:07

Megoldandó a következő háromismeretlenes harmadfokú egyenlet, t=1,2 és 3 esetén:

t2·w3+t·v·(v2-3·u·w)+u3=1

Keress összefüggést a következő ciklikus mátrixszal:

M:=\left(\matrix{u&v\root3\of{t}&w\root3\of{t^2}\cr w\root3\of{t^2}&u&v\root3\of{t}\cr v\root3\of{t}&w\root3\of{t^2}&u\cr}\right)

További előzmények: [3708],[3711],[3712],[3713]

Előzmény: [3710] nadorp, 2013-04-13 09:28:54
[3715] Lóczi Lajos2013-04-17 23:38:37

Pl. itt.

Előzmény: [3714] egyedülható, 2013-04-17 19:35:54

  [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]    [89]    [90]    [91]    [92]    [93]    [94]    [95]    [96]    [97]    [98]    [99]    [100]    [101]    [102]    [103]    [104]    [105]    [106]    [107]    [108]    [109]    [110]    [111]    [112]    [113]    [114]    [115]    [116]    [117]    [118]    [119]    [120]    [121]    [122]    [123]    [124]    [125]    [126]    [127]    [128]    [129]    [130]    [131]    [132]    [133]    [134]    [135]    [136]    [137]    [138]    [139]    [140]    [141]    [142]    [143]    [144]    [145]    [146]    [147]    [148]    [149]    [150]    [151]    [152]    [153]    [154]    [155]    [156]    [157]    [158]    [159]    [160]    [161]