KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Távoktatás Hírek Fórum Internetes Tesztverseny
Játékszabályok
Technikai információk
TeX tanfolyam
Regisztráció
Témák

 

Rendelje meg a KöMaL-t!

Támogatóink:

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Reklám:

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Fórum - Érdekes matekfeladatok

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Ön még nem jelentkezett be.
Név:
Jelszó:

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]    [34. oldal]    [35. oldal]    [36. oldal]    [37. oldal]    [38. oldal]    [39. oldal]    [40. oldal]    [41. oldal]    [42. oldal]    [43. oldal]    [44. oldal]    [45. oldal]    [46. oldal]    [47. oldal]    [48. oldal]    [49. oldal]    [50. oldal]    [51. oldal]    [52. oldal]    [53. oldal]    [54. oldal]    [55. oldal]    [56. oldal]    [57. oldal]    [58. oldal]    [59. oldal]    [60. oldal]    [61. oldal]    [62. oldal]    [63. oldal]    [64. oldal]    [65. oldal]    [66. oldal]    [67. oldal]    [68. oldal]    [69. oldal]    [70. oldal]    [71. oldal]    [72. oldal]    [73. oldal]    [74. oldal]    [75. oldal]    [76. oldal]    [77. oldal]    [78. oldal]    [79. oldal]    [80. oldal]    [81. oldal]    [82. oldal]    [83. oldal]    [84. oldal]    [85. oldal]    [86. oldal]    [87. oldal]    [88. oldal]    [89. oldal]    [90. oldal]    [91. oldal]    [92. oldal]    [93. oldal]    [94. oldal]    [95. oldal]    [96. oldal]    [97. oldal]    [98. oldal]    [99. oldal]    [100. oldal]    [101. oldal]    [102. oldal]    [103. oldal]    [104. oldal]    [105. oldal]    [106. oldal]    [107. oldal]    [108. oldal]    [109. oldal]    [110. oldal]    [111. oldal]    [112. oldal]    [113. oldal]    [114. oldal]    [115. oldal]    [116. oldal]    [117. oldal]    [118. oldal]    [119. oldal]    [120. oldal]    [121. oldal]    [122. oldal]    [123. oldal]    [124. oldal]    [125. oldal]    [126. oldal]    [127. oldal]    [128. oldal]    [129. oldal]    [130. oldal]    [131. oldal]    [132. oldal]    [133. oldal]    [134. oldal]    [135. oldal]    [136. oldal]    [137. oldal]    [138. oldal]    [139. oldal]    [140. oldal]    [141. oldal]    [142. oldal]    [143. oldal]    [144. oldal]    [145. oldal]    [146. oldal]    [147. oldal]    [148. oldal]    [149. oldal]    [150. oldal]    [151. oldal]    [152. oldal]    [153. oldal]    [154. oldal]    [155. oldal]    [156. oldal]  

Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[3938] jonas2014-09-30 15:33:19

Aha, a te bizonyításod egyszerűbb. Eltér az enyémtől, mert te nem jobbról, hanem balról szorzod meg valamivel a Vandermonde determinánst, mégpedig egy Stirling-számokból álló háromszög-mátrixszal.

Előzmény: [3936] w, 2014-09-28 14:05:41
[3937] Fálesz Mihály2014-09-28 17:59:17

Szerintem nem olyan nehéz megsejteni a választ: az &tex;\displaystyle 0,1,2,\dots,n-1&xet; számokból készített szorzat (a legkisebb pozitív szorzat), vagyis &tex;\displaystyle 1!\cdot 2!\cdot\dots\cdot (n-1)!&xet; a legnagyobb közös osztó.

Előzmény: [3935] jonas, 2014-09-28 00:07:31
[3936] w2014-09-28 14:05:41

Szerintem nagyon természetes a bizonyításod. (Az elején nyilván nem &tex;\displaystyle \prod (l-k)&xet;, hanem &tex;\displaystyle \prod (a_l-a_k)&xet; van, de ez nem zavaró.)

Én eredetileg picit máshogy olvastam:

&tex;\displaystyle \prod_{1\le i<j\le n}\frac{a_j-a_i}{j-i}=\frac{\prod_{1\le i<j\le n}(a_j-a_i)}{\prod_{k=0}^{n-1} k!}=\left(\prod_{k=0}^{n-1}k!\right)^{-1}\cdot \left|\matrix{a_1^0 & a_2^0 & \dots & a_n^0\cr a_1^1 & a_2^1 & \dots & a_n^1 \cr a_1^2 & a_2^2 & \dots & a_n^2 \cr \dots & & & \dots \cr a_1^{n-1} & a_2^{n-1} & \dots & a_n^{n-1} }\right|=&xet;

&tex;\displaystyle =\quad \left|\matrix{\frac{a_1^0}{0!} & \frac{a_2^0}{0!} & \dots & \frac{a_n^0}{0!}\cr \frac{a_1^1}{1!} & \frac{a_2^1}{1!} & \dots & \frac{a_n^1}{1!} \cr \frac{a_1^2}{2!} & \frac{a_2^2}{2!} & \dots & \frac{a_n^2}{2!} \cr \dots & & & \dots \cr \frac{a_1^{n-1}}{(n-1)!} & \frac{a_2^{n-1}}{(n-1)!} & \dots & \frac{a_n^{n-1}}{(n-1)!} }\right|\quad =\quad \left|\matrix{\binom{a_1}0 & \binom{a_2}0 & \dots & \binom{a_n}0 \cr \binom{a_1}1 & \binom{a_2}1 & \dots & \binom{a_n}1 \cr \binom{a_1}2 & \binom{a_2}2 & \dots & \binom{a_n}2 \cr \dots & & & \dots \cr \binom{a_1}{n-1} & \binom{a_2}{n-1} & \dots & \binom{a_n}{n-1} }\right|\quad \in Z.&xet;

De a feladat megoldható Vandermonde-determinánsok nélkül is.

Előzmény: [3935] jonas, 2014-09-28 00:07:31
[3935] jonas2014-09-28 00:07:31

Megsejteni nehéz, de ha már tudom, hogy mi a várt megoldás, akkor nem olyan nehéz bebizonyítani. Mutatok egy vázlatot. Ez elég ronda, szeretnék látni szebb bizonyítást.

Először írjuk fel az általad kért szorzatot Vandermonde-determináns alakban.

&tex;\displaystyle {\rm det} {\bf V} = \prod_{1\le k<l\le n} (l-k) = \left|\matrix{ a_1^0 & a_2^0 & \dots & a_n^0 \cr a_1^1 & a_2^1 & \dots & a_n^1 \cr a_1^2 & a_2^2 & \dots & a_n^2 \cr \dots & & & \dots \cr a_1^{n-1} & a_2^{n-1} & \dots & a_n^{n-1} \cr }\right| &xet;

Speciálisan írjuk fel a nevezőt is ilyen alakban.

&tex;\displaystyle {\rm det} {\bf S} = \prod_{1\le k<l\le n} (l-k) = \left|\matrix{ 1^0 & 2^0 & \dots & n^0 \cr 1^1 & 2^1 & \dots & n^1 \cr 1^2 & 2^2 & \dots & n^2 \cr \dots & & & \dots \cr 1^{n-1} & 2^{n-1} & \dots & n^{n-1} \cr }\right| &xet;

Most a célunk belátni, hogy bármilyen &tex;\displaystyle a &xet; egész számra a &tex;\displaystyle {\bf g}_a = {(}a^0, a^1, a^2, \dots, a^{n-1}{)}^{\rm T} &xet; vektort fel lehet írni az utóbbi determináns oszlopvektoraiból egész együtthatós lineáris kombinációként. Ezt teljes indukcióval lehet belátni. Vegyük észre ugyanis, hogy bármely &tex;\displaystyle 0 \le k < n &xet; egész kitevőre

&tex;\displaystyle 0 = \sum_{0\le l\le n} (-1)^l \binom{n}{l} (a-l)^k &xet;

ez ugyanis az &tex;\displaystyle a^k &xet; sorozat &tex;\displaystyle n &xet;-edik különbségsorozatának az &tex;\displaystyle a &xet; indexű eleme. Ebből

&tex;\displaystyle 0 = \sum_{0\le l\le n} (-1)^l \binom{n}{l} {\bf g}_{a-l}. &xet;

Ebben az összegben az együtthatók egészek, és a két szélső vektor, &tex;\displaystyle {\bf g}_a &xet; és &tex;\displaystyle {\bf g}_{a-n} &xet; éppen &tex;\displaystyle \pm1 &xet; együtthatóval szerepel. Ha kivonjuk a szélső tagot, akkor a maradék összeg megadja a &tex;\displaystyle {\bf g}_a &xet; illetve &tex;\displaystyle {\bf g}_{a-n} &xet; vektort az előző &tex;\displaystyle n &xet; illetve a következő &tex;\displaystyle n &xet; vektor egész együtthatós kombinációjaként. Így minden &tex;\displaystyle {\bf g}_n &xet; vektort rekurzívan kifejthetünk előre (ha &tex;\displaystyle n &xet; pozitív) vagy hátra (ha &tex;\displaystyle n &xet; nem pozitív) addig, hogy csak a &tex;\displaystyle {\bf g}_1, \dots, {\bf g}_n &xet; vektorok kombinációiból álljon, és ebben az együtthatók egészek lesznek.

Ha ezt a &tex;\displaystyle {\bf V} &xet; mátrix minden oszlopára megtesszük, akkor &tex;\displaystyle {\bf V} &xet;-t felírtuk &tex;\displaystyle {\bf S} &xet; és egy egész együtthatós mátrix szorzataként, innen &tex;\displaystyle {\rm det} {\bf V} &xet; többszöröse &tex;\displaystyle {\rm det} {\bf S} &xet;-nek.

Előzmény: [3934] w, 2014-09-27 19:57:42
[3934] w2014-09-27 19:57:42

Igen, ez a megoldás. A feladat más szóval azt kéri, hogy bizonyítsuk be, hogy

&tex;\displaystyle \prod_{1\le i<j\le n}\frac{a_j-a_i}{j-i}&xet;

egész szám bármely &tex;\displaystyle a_1,a_2,\dots,a_n&xet; egész számokra.

Kíváncsi vagyok, hogy milyen megoldási ötleteket fogtok találni.

Előzmény: [3933] jonas, 2014-09-16 23:10:19
[3933] jonas2014-09-16 23:10:19

Nem ismertem, de érdekes feladat. Szerintem ez a sorozat a megoldás rá.

Előzmény: [3932] w, 2014-09-15 17:56:02
[3932] w2014-09-15 17:56:02

Kíváncsi vagyok, hányan ismerik:

Legyen &tex;\displaystyle n&xet; pozitív egész szám, és tekintsük bármely &tex;\displaystyle S=(a_0,\dots,a_n)&xet; egész számokból álló sorozathoz a

&tex;\displaystyle f(S)=\prod_{0\le i<j\le n}(a_j-a_i)&xet;

szorzatot. Ezzel az összes ilyen számsorozathoz egy-egy egész számot rendeltünk. Mi a legnagyobb olyan pozitív egész, amely minden &tex;\displaystyle f(S)&xet; számot osztja?

[3931] w2014-09-15 17:51:48

Erre lényegét tekintve csak egyetlen bizonyítást ismerek, de jó meggondolni, hogy hányféleképpen mondható el. Talán a legrövidebb magyarázat a következő.

Vegyük észre, hogy az egyenlet ekvivalens a következő nyilvánvaló ténnyel:

&tex;\displaystyle \left|\left\{(k,a)\in N^2:\quad 0<k^ta\le x^t\right\}\right|=\left|\left\{(k,b)\in N^2:\quad 0<k^{1/t}b\le x\right\}\right|,&xet;QED.

Megjegyzés. Ha nadorp gondolatmenetét akarjuk átvinni, a következő szemléletesebb modellel lehet a legérdekesebb elmondani (lásd akár a 2013-as IMO shortlist A4 feladatát). Rajzoljunk egy oszlopdiagramot a derékszögű koordinátarendszer első síknegyedébe, méghozzá úgy, hogy az &tex;\displaystyle x&xet;-tengelyen a &tex;\displaystyle k&xet;-adik egységszakasz fölé &tex;\displaystyle \left[\frac{x}{k^{1/t}}\right]&xet; magasságú oszlopot rajzolunk. Az oszlopok együttes területe így a jobb oldalt adja ki, és persze az oszlopok "ereszkednek". Most képzeljük el mindezt, mint egy sordiagramot: nézzük meg, hogy milyen hosszú sor lóg ki az &tex;\displaystyle y&xet;-tengely &tex;\displaystyle k&xet;-adik egységszakaszán. Ez a sor éppen addig tart, amíg az &tex;\displaystyle a&xet;-adik oszlop magassága legalább &tex;\displaystyle k&xet;, avagy amíg

&tex;\displaystyle \left[\frac{x}{a^{1/t}}\right]\ge k,&xet;

&tex;\displaystyle \frac{x}{a^{1/t}}\ge k,&xet;

&tex;\displaystyle \frac{x^t}{k^t}\ge a,&xet;

&tex;\displaystyle \left[\frac{x^t}{k^t}\right]\ge a.&xet;

Más szóval, az (alulról) &tex;\displaystyle k&xet;-adik sor hossza éppen &tex;\displaystyle \left[\frac{x^t}{k^t}\right]&xet;, és ezzel kaptuk, hogy a bal oldali összeg is a diagram területét adja ki.

Előzmény: [3930] w, 2014-09-09 19:55:20
[3930] w2014-09-09 19:55:20

Az általánosításban szükségszerű pozitív egészekre szorítkozni? Igaz-e, hogy ha &tex;\displaystyle x,t>0&xet;, akkor

&tex;\displaystyle \sum_{k=1}^\infty \bigg[\frac{x^t}{k^t}\bigg]=\sum_{k=1}^\infty \bigg[\frac x{k^{1/t}}\bigg].&xet;

Előzmény: [3929] nadorp, 2014-09-09 10:23:38
[3929] nadorp2014-09-09 10:23:38

Ha &tex;\displaystyle 1\leq k\leq n^2&xet; egész és &tex;\displaystyle \left[\frac{n}{\sqrt{k}}\right]=a&xet;, akkor nyilván &tex;\displaystyle 1\leq a\leq n&xet; ,továbbá

&tex;\displaystyle \frac{n^2}{(a+1)^2}<k\leq\frac{n^2}{a^2} &xet;(1)

Legyen &tex;\displaystyle I_a=\bigg(\frac{n^2}{(a+1)^2};\frac{n^2}{a^2}\bigg]&xet; balról nyílt, jobbról zárt intervallum (&tex;\displaystyle 1\leq a\leq n&xet; egész). Ekkor az &tex;\displaystyle I_a&xet; intervallumok diszjunktak, uniójuk tartalmazza az összes egészt 1 és n között, mégpedig mindegyik &tex;\displaystyle I_a&xet; pontosan &tex;\displaystyle \left[\frac{n^2}{a^2}\right]-\left[\frac{n^2}{(a+1)^2}\right]&xet; egészt tartalmaz. Mivel &tex;\displaystyle k\in I_a&xet; pontosan akkor teljesül, ha &tex;\displaystyle \left[\frac{n}{\sqrt{k}}\right]=a&xet;, ezért

&tex;\displaystyle \sum_{k=1}^{n^2}\left[\frac{n}{\sqrt{k}}\right]=\sum_{a=1}^{n}\sum_{k\in I_a}\left[\frac{n}{\sqrt{k}}\right]=\sum_{a=1}^{n}a\left(\left[\frac{n^2}{a^2}\right]-\left[\frac{n^2}{(a+1)^2}\right]\right)=\sum_{a=1}^{n}\left[\frac{n^2}{a^2}\right]&xet;

Általánosítás:

Tetszőleges n,m pozitív egészre

&tex;\displaystyle \sum_{k=1}^{n^m}\left[\frac{n}{\root{m}\of{k}}\right]=\sum_{k=1}^{n}\left[\frac{n^m}{k^m}\right]&xet;

Előzmény: [3928] w, 2014-09-03 16:17:04
[3928] w2014-09-03 16:17:04

Jelölje &tex;\displaystyle [x]&xet; az &tex;\displaystyle x&xet; egészrészét. Bizonyítsuk be, hogy

&tex;\displaystyle \left[\frac{n^2}{1^2}\right]+\left[\frac{n^2}{2^2}\right]+\dots+\left[\frac{n^2}{n^2}\right]=\left[\frac{n}{\sqrt{1}}\right]+\left[\frac{n}{\sqrt{2}}\right]+\dots+\left[\frac{n}{\sqrt{n^2-1}}\right]+\left[\frac{n}{\sqrt{n^2}}\right].&xet;

Keressünk általánosítást is.

[3927] Loiscenter2014-08-13 10:37:02

Nagyon köszönöm szépen Lóczi Lajos ellenpéldát.(elnézés a elözö irás Névhibáért)

Hozá kell még pontositanom hogy k, n pozitiv egész!

Előzmény: [3926] Loiscenter, 2014-08-13 10:10:59
[3926] Loiscenter2014-08-13 10:10:59

Nagyon köszönöm szépen Loci Láo ellenpéldát.

Hozá kell még pontositanom hogy k pozitiv egész!

Előzmény: [3925] Lóczi Lajos, 2014-08-12 22:42:02
[3925] Lóczi Lajos2014-08-12 22:42:02

Nem. Pl. &tex;\displaystyle n=2&xet;, &tex;\displaystyle x_1=1/2&xet;, &tex;\displaystyle x_2=3/2&xet; és &tex;\displaystyle k=-2&xet; ellenpélda.

Előzmény: [3924] Loiscenter, 2014-08-12 18:31:27
[3924] Loiscenter2014-08-12 18:31:27

Legyenek &tex;\displaystyle x_1&xet; , &tex;\displaystyle x_2&xet; , ... , &tex;\displaystyle x_n&xet; pozitiv számok, melyeknek összegük n azaz &tex;\displaystyle x_1 + x_2 +...+ x_n = n&xet;.

Igaz -e a következö egyenlötlenség:

&tex;\displaystyle x_1^k.x_2^k...x_n^k &xet; ( &tex;\displaystyle x_1^{k+1}&xet; + &tex;\displaystyle x_2^{k+1}&xet; +....+ &tex;\displaystyle x_n^{k+1}&xet; ) =< &tex;\displaystyle x_1^k+x_2^k +....+ x_n^k .&xet;

[3923] Loiscenter2014-08-12 17:59:22

Multkor kéedeztem a következö feladatot

ROKA SÁNDOR: 2000 feladat.... ( 1780. feladat) Adott 35 pozitiv egész szám, amelyek összege 100, és egyikük sem nagyobb 50-nél. Bizonyitsuk be, hogy van köztük néhány olyan, amelyek összege 50.

Most Ehhez a témához kapcsolatban szeretnék segitséget megint kérni. A szakirodalmakrol és közelálló eredményekrol adnatok valamilyen tampontot hogy elinduljak! köszönöm szépen elöre! N.V. Loi.

[3922] Loiscenter2014-07-29 11:01:37

Megjegyzés Erben Péter munkajaval kapcsolattal: 1)Nagyon tetszik nekem a algoritmus és egyenlőtlenség kombinácio alkalmazását. Sötszerintem általanos fejlesztéshez ezen az irányon érdemes menni. 2) köszönöm a Pataki J. munkahoz hozzáférhetöget. 3). szeretnek tovabb menni a khövetkezö iranyba: 2n (k.n)osszegu es egyenkent sulya nem nagyobb n-nel. Mi a legkisebb m szam hogy ket (k) egyenlö részre bonthatoság. ehhez tudtok -e irodalmat forrását segiteni nekem esetleg az tapasztalatokat, javaslatokat is!!! nagyon köszönöm szépen a segitségeteket!!!

Nguyen Van Loi.

Előzmény: [3920] Erben Péter, 2014-07-28 22:51:14
[3921] Loiscenter2014-07-29 10:46:16

Elöbb szeretném folytatni a gondolataimat: Most tekintjük azt az esetet, amikor maximum csak 8 csoportra oszthato a számokat.legyen ezek A1, A2, A3,..., A8 növekvö összegü sorendben. A1,A2,...,A5 5-ösból kivalaszthato nehány tagot , melynek összege oszthato 25 -tel. ez csak 25 lehet ( mert 50-est kizarjuk, 75-est nem éri el azért mert utolso 2 tag összege nagyobb 25 -nél). 1)csak azt az esetet kell foglalkozni, amikor legalabb 3 tag van benne az 25-ösben.==> van 5-ös összegü tag. legyen ez A1=5. 2)Vesszük A2, A3,..., A6 -t , ebben megint talaljuk legalább 3 tagu 25-ös összeget. megint van 5-ös összegü tag. legyen ez A2=5. 3)Valasszuk ki A3, A4,..., A7. Ha ennek összege 75, akkor A8=15. A kompozicio:( 5, 5, 15, 15, 15, 15, 15, 15 ) ebböl 5+ 15+15+15=50 jo. Más különben megint van 5-ösöm. Legyen ez A3=5. 4) most vesszük A1, A2, A3,A7, A8. Ha összege 75 akkor A4+A5+ A6=25. ==> A4=5, ezért A7+A8=60, ebben csak 30+30 lehet. megint tudjuk 50-est kombinálni. 5)Hanem, akkor megint van 25-ös. tehat A4 = 5 vagy A4=10. 6)A felmaradó 3 tagbol egyik sem lehet 25, osszegük pedig legalább 75, kell hogy legyen. ezért van 30-nal nem kisebb tag ez legyen A8. igy vagy vele vagy masik ket taggal tudjuk kombinalni 50-est. kész.

Előzmény: [3920] Erben Péter, 2014-07-28 22:51:14
[3920] Erben Péter2014-07-28 22:51:14

Itt még sokkal több érdekesség olvasható a feladatról (a 64. oldaltól).

Előzmény: [3919] Erben Péter, 2014-07-28 22:33:54
[3919] Erben Péter2014-07-28 22:33:54

Ha &tex;\displaystyle k=1&xet;, akkor tehát az történt, hogy a 7 legnagyobb súlyt már be tudtuk pakolni, és az utolsó (&tex;\displaystyle b_1&xet;) nem fér egyik tartályba sem. Ebből következik, hogy &tex;\displaystyle b_1>1&xet;. Sőt, &tex;\displaystyle b_1=2&xet;, mert &tex;\displaystyle b_1\ge 3&xet;-ból az következne, hogy a súlyok összege legalább 24.

Továbbra is az összegre figyelve kiderül, hogy legalább 4 darab 2-es van. (&tex;\displaystyle 2+7\cdot 3 > 20&xet;, &tex;\displaystyle 2\cdot 2+ 6\cdot 3>20&xet;, stb.) Ha van 5 darab kettes, akkor kész vagyunk.

Ha pont 4 darab 2-es van, akkor a maradék 4 súly mind 3. Ebben az esetben &tex;\displaystyle 2+2+3+3&xet; megoldás.

Megjegyzés: A &tex;\displaystyle p(k)&xet; polinom általában is segít megtalálni egy olyan &tex;\displaystyle m&xet; számot, ami fölött mindig megy a kiválasztás. Amikor 100 az összeg, akkor az derül ki, hogy &tex;\displaystyle m=35&xet; a határ. (Ott is a &tex;\displaystyle k=1&xet; esettel kell külön megküzdeni.) &tex;\displaystyle m=34&xet;-re a 33 darab 3-as és 1 darab 1-es esetén nem állítható elő az 50.

Előzmény: [3918] Erben Péter, 2014-07-28 22:17:51
[3918] Erben Péter2014-07-28 22:17:51

Megpróbálom leírni a kisebb feladatra, onnan lehet általánosítani.

Adott tehát 8 pozitív egész, összegük 20, egyik sem több, mint 10. Szeretnénk kiválasztani közülük néhányat, amelyek összege 10.

Megadunk egy algoritmust, ami sok esetben megadja a megoldást. Ha mégsem, azokkal az esetekkel elbánunk valahogy.

Algoritmus: A számokat súlyoknak tekintjük, amiket két 10 kg kapacitású "tartályba" próbálunk bepakolni a következő módon. Súly szerint csökkenő sorrendben haladunk, és a soron következő súlyt berakjuk valamelyik tartályba, ahova még elfér. Soha nem lépjük át a 10 kg-os határt. Ha végigmegy az algoritmus, akkor örülünk. Ha nem, akkor megvizsgáljuk, hol akadtunk el.

Az elakadás szükséges feltétele: Legyenek a súlyok: &tex;\displaystyle b_8\ge b_7 \ge \dots \ge b_1&xet;. Tegyük fel, hogy a &tex;\displaystyle k&xet;. súly az első, amit már egyik tartályba sem tudunk berakni. Ha a tartályokban pillanatnyilag megmaradt szabad kapacitás &tex;\displaystyle h_1&xet; és &tex;\displaystyle h_2&xet;, akkor az elakadás azt jelenti, hogy &tex;\displaystyle b_k>h_1&xet; és &tex;\displaystyle b_k>h_2&xet;. Egészekrők van szó, vagyis &tex;\displaystyle b_k\ge h_1+1&xet; és &tex;\displaystyle b_k\ge h_2&xet;.

Most felhasználjuk, hogy a szabad kapacitások összege pontosan a még be nem pakolt súlyok összege.

&tex;\displaystyle 2b_k\ge h_1+ h_2 +2 = b_1+b_2+\dots+b_{k-1}+b_k+2 \rightarrow b_k \ge b_1+b_2+\dots+b_{k-1}+2 \ge k+1&xet;

Alulról becsülve az összes súly összegét:

&tex;\displaystyle 20=b_1+b_2+\dots+b_8 = (b_1+\dots+b_{k-1})+(b_k+\dots+b_8)\ge k-1+(8-k+1)\cdot(k+1)&xet;

Rendezés után &tex;\displaystyle k^2-9k+12\ge 0&xet; adódik. Csak olyan &tex;\displaystyle k&xet; indexű súlynál akadhat el az algoritmus, amire a &tex;\displaystyle p(k)=k^2-9k+12&xet; polinom nemnegatív. Az fog kiderülni, hogy nem sok ilyen &tex;\displaystyle k&xet; van.

A &tex;\displaystyle p(k)&xet; csak &tex;\displaystyle k=1&xet; és &tex;\displaystyle k=8&xet; esetén nemnegatív, a minket érdeklő halmazon.

&tex;\displaystyle k=8&xet; nem lehetséges, mert feltettük, hogy minden súly legfeljebb 10. Marad tehát a &tex;\displaystyle k=1&xet; eset, ott még kell egy kicsit dolgozni. (Folyt. köv.)

Előzmény: [3917] csábos, 2014-07-28 21:28:13
[3917] csábos2014-07-28 21:28:13

Mostmár szívesen látnám a hivatalos megoldást. Akár a Pataki tanár úr félét.

Előzmény: [3916] Erben Péter, 2014-07-28 19:42:26
[3916] Erben Péter2014-07-28 19:42:26

Innen már tényleg kevés van hátra.

A 8 tag esete az eredeti probléma kisebb változata. Legyenek a &tex;\displaystyle b_1, b_2,\dots,b_8&xet; a tagokban lévő számok összegének ötödével egyenlők. Így &tex;\displaystyle b_1+b_2+\dots+b_8=20&xet;, és &tex;\displaystyle b_i\le 10&xet;. Megmutatható, hogy kiválasztható közülük néhány, amelyek összege 10. A kiválasztott &tex;\displaystyle b_i&xet;-k megadják az eredeti feladat megoldását: a nekik megfelelő tagokban lévő számok összege 50.

Előzmény: [3915] Loiscenter, 2014-07-28 15:23:48
[3915] Loiscenter2014-07-28 15:23:48

Nagyon jo ötletet meritettem a hozzászólásotokböl.

Most tekintjuk azt legfinomabb felosztást, melyre csak 7 csoport a maximális. 1) csoportok közti szamok különbsége oszthato 5-tel. 2) (LEGFONTOSABB): csorton belül szamok különbsége is rendelkezik ezzel a tulajdonsaggal.( különben csinálhatjuk egy rossz cserét). összegezve : 35 számokbol bármelyik kettönek különbsége osztható 5-tel. 3)vannak 3-nal kisebb szám. tehat vagy 1, vagy 2( és kizárják egymást). a)ha legkisebb szám 2. akkor alap 2.35=70. ezért mar csak legfeljebb(30:5)=6 darab 7-nal nem kisebb szam lehet. azaz legalább (35-6)=29 darabb 2-es van ==> kivalasztható 25-öt , kész.(ez pont Erben P. esete) b) ha legkisebb szam 1-es. akkor alap: 35. csak (65:5=13 darab 6-nál nem kisebb. azaz (35-13)=22 darab 1-es van legalabb. tehat van 4 csoport , melynek összege 5 ( összesen 20) és 3 csoport, melynek összege 80.téhát van 30-nal nagyobb összegü. ennek összege csak 50-nal nagyobb lehet:55,60,65,70.(mert van még két csoport).ebbol a csoportbol 2 darabb legnagyobb szam kicerélem a legkiebb-be igy csokkenthetjuk 50 alá az összeget. Tovább kiegészithetem 1-essekkel 50-re. téhat a 7-es csoport esete el van intézve. csak 8-as csoport esete maradt. (de jo !!!!)

Előzmény: [3914] csábos, 2014-07-28 10:51:42
[3914] csábos2014-07-28 10:51:42

A csoportok közti csere azt jelenti, hogy ha pontosan 5 elemből áll egy csoport, és van két ilyen is, akkor egy-egy elemet cserélve újabb 5-ösöket kapunk, amelyekből szintén kiválasztható néhány szám. amely összege osztható 5-tel. Ha a cserélt számok nem kongruensek egymással modulo 5, akkor kisebb csoportokat kapunk. Így feltehető, hogy ha van több 5-ös csoport, akkor az összes azokban lévő elem páronként kongruens modulo 5.

Előzmény: [3913] Erben Péter, 2014-07-28 07:24:17

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]    [34. oldal]    [35. oldal]    [36. oldal]    [37. oldal]    [38. oldal]    [39. oldal]    [40. oldal]    [41. oldal]    [42. oldal]    [43. oldal]    [44. oldal]    [45. oldal]    [46. oldal]    [47. oldal]    [48. oldal]    [49. oldal]    [50. oldal]    [51. oldal]    [52. oldal]    [53. oldal]    [54. oldal]    [55. oldal]    [56. oldal]    [57. oldal]    [58. oldal]    [59. oldal]    [60. oldal]    [61. oldal]    [62. oldal]    [63. oldal]    [64. oldal]    [65. oldal]    [66. oldal]    [67. oldal]    [68. oldal]    [69. oldal]    [70. oldal]    [71. oldal]    [72. oldal]    [73. oldal]    [74. oldal]    [75. oldal]    [76. oldal]    [77. oldal]    [78. oldal]    [79. oldal]    [80. oldal]    [81. oldal]    [82. oldal]    [83. oldal]    [84. oldal]    [85. oldal]    [86. oldal]    [87. oldal]    [88. oldal]    [89. oldal]    [90. oldal]    [91. oldal]    [92. oldal]    [93. oldal]    [94. oldal]    [95. oldal]    [96. oldal]    [97. oldal]    [98. oldal]    [99. oldal]    [100. oldal]    [101. oldal]    [102. oldal]    [103. oldal]    [104. oldal]    [105. oldal]    [106. oldal]    [107. oldal]    [108. oldal]    [109. oldal]    [110. oldal]    [111. oldal]    [112. oldal]    [113. oldal]    [114. oldal]    [115. oldal]    [116. oldal]    [117. oldal]    [118. oldal]    [119. oldal]    [120. oldal]    [121. oldal]    [122. oldal]    [123. oldal]    [124. oldal]    [125. oldal]    [126. oldal]    [127. oldal]    [128. oldal]    [129. oldal]    [130. oldal]    [131. oldal]    [132. oldal]    [133. oldal]    [134. oldal]    [135. oldal]    [136. oldal]    [137. oldal]    [138. oldal]    [139. oldal]    [140. oldal]    [141. oldal]    [142. oldal]    [143. oldal]    [144. oldal]    [145. oldal]    [146. oldal]    [147. oldal]    [148. oldal]    [149. oldal]    [150. oldal]    [151. oldal]    [152. oldal]    [153. oldal]    [154. oldal]    [155. oldal]    [156. oldal]  

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Támogatóink:   Ericsson   Google   Szerencsejáték Zrt.   Emberi Erőforrások Minisztériuma   Emberi Erőforrás Támogatáskezelő   Oktatáskutató és Fejlesztő Intézet   ELTE   Nemzeti Tehetség Program   Nemzeti
Kulturális Alap