Kombinatorika

Tarcsay Tamás, Nov 2, 2019

Kombinatorikus geometriai problémák

Table of Contents

  1. Hány részre osztja
    1. Legfeljebb hány részre osztja ...
    2. gyk_86 - Ötszög
    3. Emelt érettségi 2021. május, 2.
    4. Emelt érettségi 2019.május, 7.
    5. Emelt érettségi 2018. május, 8.
    6. Emelt érettségi 2016. október, 9.
    7. Emelt érettségi 2008. május, 7.
  2. Kombinatorika feladatok
    1. gyk_215 - Ismétléses kombinációs problémák
    2. Emelt érettségi 2022. május, 5.
    3. Emelt érettségi 2022. május, 8.
    4. Emelt érettségi 2021.október, 4.
    5. Emelt érettségi 2020. október, 2.
    6. Emelt érettségi 2020. október, 5.
    7. Emelt érettségi 2020. október, 9.
    8. Emelt érettségi 2022. október, 5.
    9. Emelt érettségi 2018. október, 5.
    10. Emelt érettségi 2018. május, 3.
    11. Emelt érettségi 2018. május, 5.
    12. Emelt érettségi 2017. október, 3.
    13. Emelt érettségi 2017. május, 8.
    14. Emelt érettségi 2016. október, 4.
    15. Emelt érettségi 2016. október, 6.
    16. Emelt érettségi 2016. október, 9.
    17. Emelt érettségi 2016. május, 2.
    18. Emelt érettségi 2016. május, 6.
    19. Emelt érettségi 2015. október, 4. b)
    20. Emelt érettségi 2015. október, 6.
    21. Emelt érettségi 2015. május, 3.
    22. Emelt érettségi 2015. május, 8.
    23. Emelt érettségi 2014. október, 6.
    24. Emelt érettségi 2014. október, 7.
    25. Emelt érettségi 2014. október, 8.
    26. Emelt érettségi 2014. május, 1.
    27. Emelt érettségi 2014. május, 9.
    28. Emelt érettségi 2013. május, 3.
    29. Emelt érettségi 2013. május, 8.
    30. Emelt érettségi 2012. október, 5.
    31. Emelt érettségi 2012. május, 6.
    32. Emelt érettségi 2011. október, 9.
    33. Emelt érettségi 2010. október, 6.
    34. Emelt érettségi 2010. október, 8.
    35. Emelt érettségi 2009. október, 5.
    36. Emelt érettségi 2009. október, 7.
    37. Emelt érettségi 2009. május, 9.
    38. Emelt érettségi 2008. október, 6.
    39. Emelt érettségi 2007. október, 8.
    40. Emelt érettségi 2007. május, 7.
    41. Emelt érettségi 2006. október, 2.
    42. Emelt érettségi 2006. február, 2.
    43. Emelt érettségi 2006. február, 7.
    44. Emelt érettségi 2005. október, 2.
    45. Emelt érettségi 2005. október, 8.
    46. Hány olyan metszéspontja van ...
    47. Hány rácspont ...
    48. Egy zárt ...
    49. Hány rácspont ... (3.)
    50. Hány olyan négyjegyű ...
    51. 2025. 122.
    52. 2025. 166.
    53. 2025. 186.
    54. 2025. 188.
    55. 2025. 189.
    56. 2025. 227.
    57. 2026. 48.
    58. 2026. 77.
    59. 2026. 101.
    60. 2026. 107.
    61. 2026. 110.
    62. 2026. 129.
    63. 2026. 133.

1.

Hány részre osztja

  • 1. Legfeljebb hány részre osztja ...
  • 2. gyk_86 - Ötszög
  • 3. Emelt érettségi 2021. május, 2.
  • 4. Emelt érettségi 2019.május, 7.
  • 5. Emelt érettségi 2018. május, 8.
  • 6. Emelt érettségi 2016. október, 9.
  • 7. Emelt érettségi 2008. május, 7.

1.1.

Legfeljebb hány részre osztja ...

[br][list=1][*]az egyenest [i]n [/i]pontja;[/*][*]a síkot [i]n[/i] egyenese;[/*][*]a teret [i]n [/i]síkja;[/*][*]a [i]k[/i]-dimenziós teret [i]n[/i] darab  [i]k[/i]-1 dimenziós hitpersíkja ("Elvetemült geométereknek").[/*][/list][right]([url=https://www.geogebra.org/u/szilassi]Dr. Szilassi Lajos[/url] javaslatára)[/right][right][/right]
1.
[size=85][code][/code]Tétel: az egyenest [i]n[/i] pontja [i]n [/i]+ 1 részre ([i]n[/i] -1 szakasz és két félegyenes) osztja. ezt így jelöljük:[br][justify][math]R_1\left(n\right)=n+1[/math]. (Az [i]R[/i] alsó indexe a dimenziószámra utal.)[br]A tétel elég nyilvánvaló, aki akar, az gondolkodjon el a bizonyításon![br][br][/justify][/size]
2.
[size=85]Maximális számú síkrész akkor jön létre, ha az egyenesek között nincsenek párhuzamosak, különböző pontokban metszik egymást.[/size][br][size=85]A fenti GeoGebra fájl alapján a keletkezett síkrészek száma:[/size]
[size=85]Ismerősök ezek a számok?[br][/size][size=85]Egészítsük ki a fenti táblázatot a[url=https://www.geogebra.org/m/mqmpckm8] háromszögszámok[/url] sorával![/size]
A sejtés ...
[size=85]ezek alapján már adódik: [math]R_2\left(n\right)=\frac{n\left\langle n+1\right\rangle}{2}+1[/math][/size].
A bizonyítás ...
[size=85]például [url=https://hu.wikipedia.org/wiki/Teljes_indukci%C3%B3]teljes indukció[/url]val (is) történhet.[br][/size][size=85][i]n[/i][/size][size=85]= 1-re igaz az állatás.[br][/size][size=85]Tegyük fel, hogy adott a síkon [i]n[/i] páronként nem párhuzamos egyenes, amelyek különböző pontokban metszik egymást, és [/size][img]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAI4AAAAiCAYAAACJI+GdAAAFaElEQVR4Xu3az7HjRBAG8N0MCEEZQAaYC8WRDFAGLBmYDAjBXLgCGZg7VUAGIgIgApjf1vTW1DzJGsl/8LPVVV2SZrp7evr7pmX7vbdvNtkqsKICb1f4bC5bBd5sxGknwT6Z0nuQ71IS7/7PRDbitFW/S2ZfJgXYLeWjtNjXSX9O+nux8CET5+9bJlOutRGnrfIIo9tcAqg+xQH8nOySAcLqLPRYOHyS7mlLnLl1Vs1vxGkr2yVfDQiAFK3CHmlL4vBFmr41yKXtnpE4TqrXzk9JvQq6fJ16DbEl7Al7YwGkeOIAsqUj8dstAJL9vlgvXHUhOQ0LYl3M9BmJo+A+LyBKn+8BA/Qx8tTdhg/Afkv6Tb5HJGpuThBhN2dUzLOXn2spyGrcfm4uz0icLgOs8FH0Q7pHhugqAcQYODpMxIhuJE7Y1iAiyb/FYE1EU38knepWCIMgrrWMxboJiZ6ROApbgzGkMYSowZs61QDTtRCOIBxwjdWyqwbGwOa3EecmlD9vER0gDg3CAD1eN3XXQY6+Wg7Q7IekyOW5SyrWGHlK92N6qMl0ajfs5edayhSpz6tMo/e1O47NKehcMaWr6ICYOnmNW5o1AxogAjz31gSMqxxKiddREKokCjtx2Ogk9lATr07IOrH2bLLJQO3kWMd9l8fqfFtinm0zRhyFsbGPk/6ZC6kgTun3SZcAa7P9Ah/2AdTZm5sI0KVxCkBiv3IEwBToSAEowneX9FDENwfgiHkqdzb854RNbbcvnKzfzwU5c15t6FDHOdVxEASIUYzyVLWQxyYVc+4EljlFscoCnbn3i7gjjpxa9j23ILCBfo44yHRpHCRo2UOX7OQJD/i/wGOKOJLydbOe13U+y8HmNr62e6z1m8vnnHmFjINzTpxL+a4l8pLOKNcgTDNxLKBQGBfi+ZBUEedYyxb5ygXrtmdeR6qFz9JOdSlATsWR14sC3mLhkTUQB0ZLRf7HrC2+sd8X+57qOE498MKhT/fIINmhYcUx8I0hD/9QBRC3JOIY6cold+mh/F1kLJ1fGnJ8RpOrEweQQRKdAVjIUwOMCIcRBBAPKY55TgwSMWyAmI/NRBhrRcerQ1tPDNcpkeMh6VxXPBHiYaei1ureIoFTXD/4jHUcIAtcgoMEQ1JXAjzgsDW2q7LgX48x0cV0FLEIcMdIMOVfLbP48fPk8cVir/t3+DWl+MNImnDqinGYqH3U35Ra0zHZ58G4frAZI47TbgEAh0TwCHBIE+wAX/6YFvZ1xzGOIIjTZSPx+7yOuegQ1j7Vcfx/ypx8O2fwpPPwCyxbShB4x/WDzxhxgC54dBfGQPUsAOCHHEHHMVaSzJQxJBErhE2QxdghryNWqPE+ryHGJpetgJoes7ZEDgxeYFESZ5cifZrUaQe4H/ssQlyDCEjkXpdApug8ZSIIEqSKcYsPSQ95wLNu5Q98JcGM16QrY2/36yugtrCkp6RLk18ljYYQfIDfe1nyJ4ddsucYzp4lgCCArsVidSeayff99Fq/lti3sHGg+qSuxOFy2O5BHHKYjeG1KL8lxCkDK4Y/SZB/JggiySEToTWpKLj4r1X2KXFK7EcddknvgTzIfJE81hKnFVQEUMSWZG2KrUK/VtF9f0zq1/Uhb2LJr+2vZt/XJg4y0CjiqcJ0jXb3XFx7Rfx4PXn+KxPpeM+JL83t2sRZms+j2feZSDrRQ8lGnOvBqdv4EOoLwtkfRq+X5rrIG3HW1a3F65CM9g/w+h3d60acFgost/E5B3F8KdB5ukfrOhtxlpNizgNhfCCOb5JI408gw5zja5rfiHNZtJCkHwnplfVQshHnoeC83WY24tyu1g+10n8azzUyLN5A7AAAAABJRU5ErkJggg==[/img][size=85]részre ontják a síkot. Egy ([i]n[/i] + 1). egyenes egyikükkel sem párhuzamos és nem megy át a korábbiak egyik metszéspontján sem. Ezt az egyenest a korábbiak különböző pontokban metszik, és - a korábbiak szerint [/size][img]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAF0AAAATCAYAAADyIwHfAAAC8ElEQVRYR+3YgY0TQQwF0LsKoITQAXSwdEAHhA4oISVQwpZACVsCVEA6ACoAP2kcWcnkMtwld0GKJWv3Zr/t729PkLi/u9mzK3D/7BVvBe8uLfqH0PhX+DKg9dvA8HkA+19Djom+jq6+NAG+xnMqgvh7xFYB+tx8BA+TNb+NBlwp7nXw+hj+u7dEx0QX9DP8Tfi2NUbEH+HvwkdEMRzDs+mjpu4c7oZcm01BaBkgBZe3lnab/Zhjomva1hE6zfuo6LD/uuVZR12O8DUZ8Q4EfIBgYodF17StW5ekc3uvZ8dqEpzJk2aQNsCZp/y52TVPL/Yc4qslt1u6hE+tvr9Hbu4mcHzUEnsQc2zTk5ifCORW4XMjO1KUsGI1xzQsT4qNiJ8d31OIzAtnQCl+rZdDevUACXk/tfwVtm49/Inn+1YbH1zUO2VwfNQSexDTE11j9ffc3wQUvLSKq3hqQoN1m5MQnO/bgoedm8vHDFfDiXMmN9yUyc70JDAOantnaqyb75eBqcOFw6va95azR3HTDvO5w/REJwIhVyWTYtvwmgBhfpA0zpbWiJhqmjZEJj9crZPn6sl9bnN71MtbpE+DV2/f8lbm+bqDE6unnm3aYT53mJ7oiBBGkTTJc9vzbIoXfpA0zuSAX0oOTTgXw1IA8atwNZjvBp/ClBS7fwNycPVbvhNhHd4TA6e5cYPfhuPFl16ycoYnH7XEHsT0RNc8cZCrjTiTgCDIT817ROomZQ5nxEq8HHKu9mr1YkcbPYUzCPXyqUf96AWfhwzvXq/HYvSmzkFMFd20EUhb4oWzJGYgiLKpeY/IKr4Rr26rHOK3LT43zBlPQ5Ynrnx68iuulS9+6pwSXOH92GNk9L7e+zjXfp7y3wBTJOK1iVpLI4qb9qi5CQjW4Y/GXhqn1+UcRR4rumnaVCLtb2ry8p3oddtPcb7klp+q/WzfHyv6KEGibwc3xJAMc+Sqj9a/StylRb/Kpl+a1E30F5jATfQXEP0viQqnFBlr/eYAAAAASUVORK5CYII=[/img] [size=85]részre bontják. Minden így kapott egyenes rész két részre bont egy korábbi síkrészt. Ezek szerint:[br][/size][math]R_2\left\langle n+1\right\rangle=R_2\left\langle n\right\rangle+R_1\left\langle n\right\rangle[/math][br][size=85]Felhasználva az indukciós feltételt és a korábbiakat,[br][math]R_2\left\langle n+1\right\rangle=\frac{n\left\langle n+1\right\rangle}{2}+1+n+1=\left\langle n+1\right\rangle\left\langle\frac{n}{2}+1\right\rangle+1=\frac{\left\langle n+1\right\rangle\left\langle n+2\right\rangle}{2}+1[/math][br][/size][size=85]Az állítást bebizonyítottuk.[/size]
3.
[size=85]Akkor osztja maximális számú részre a teret [i]n[/i] sík, ha nincsenek közöttük párhuzamosak, különböző egyenesekben metszik egymást. és e metszésvonalak is különböző pontokban metszik egymást. Legyen adott [i]n[/i] ilyen sík! Vegyünk hozzá egy ([i]n[/i] + 1). síkot úgy hogy a korábbiakat a korábbiaktól különböző egyenesekben messe, és ne menjen át a korábbi metszésvonalak metszéspontjain! Ezt a síkot a korábbi síkok [i]n [/i]egyenesben metszik, és a korábbiak szerint azt [math]R_2\left\langle n\right\rangle[/math] részre osztják. Minden ilyen síkrész két részre oszt egy korábban már meglevő síkrészt. Ezek szerint igaz a következő rekurzió:[/size][size=85][br][math]R_3\left\langle n+1\right\rangle=R_3\left\langle n\right\rangle+R_2\left\langle n\right\rangle[/math][/size].[br][size=85]Nyilvánvaló, hogy [math]R_3\left\langle1\right\rangle=2[/math]. Ennek és a korábbiaknak felhasználásával kapjuk, hogy[/size][br]
[size=85]Egy jó sejtés kéne. Ennek megtalálásában segíthet a GeoGebra görbeillesztési funkciója:[/size]
[size=85]Csak nem igaz az, hogy:[br][math]R_3\left\langle n\right\rangle=\frac{n^3+5n+6}{6}[/math][/size][math]=\frac{\left\langle n+1\right\rangle\left\langle n^2-n+6\right\rangle}{6}[/math]?[br][size=85]A bizonyítást az olvasóra bízzuk.[/size]
4.
[size=85]"Elvetemült geométer" nem lévén, a korábbiak alapján csak egy rekurzió felvetését kockáztatjuk meg:[br][math]R_{k+1}\left\langle n+1\right\rangle=R_{k+1}\left\langle n\right\rangle+R_k\left(n\right)[/math][/size]. (1)
[size=85]Ha ezt a rekurziót helyesnek fogadjuk el, akkor a következőkre jutunk:[/size]
[size=85]A sejtés megtalálásához megint illesszünk görbét![/size]
Sejtés:
[size=85][math]R_4\left\langle n\right\rangle=\frac{n^4-2n^3+11n^2+14n+24}{24}[/math][/size]
Ha igaz, akkor itt tartunk most.
Lehet, hogy érdemes böngészni.
Dr. Németh Zoltán tanár úr javaslatára ...
[size=85]vizsgáljuk a következő sorozatot![br][math]N_k\left\langle n\right\rangle=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{k}[/math][/size],[size=85] ha[/size] [math]n\ge k[/math].
A sorozat első néhány tagja:
Sejtés a fentiek alapján:
[math]R_k\left\langle n\right\rangle=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{k}[/math], [size=85]ha[/size] [math]n\ge k.[/math][br][br][size=85]A bizonyítás - bizonyára - történhet az (1) rekurzió felhasználásával. [br][br][/size][size=100][size=150]És még egy kérdés [url=https://www.math.u-szeged.hu/~nemeth/]Dr. Németh Zoltán[/url] tanár úrtól:[/size][/size][br][br][size=85]Az [math]R_k\left\langle n\right\rangle[/math][/size] [size=85]rész között hány korlátos van?[/size]
Források:
[list=1][*][size=85][/size][size=85][url=http://www.math.ubbcluj.ro/~andrasz/CD/INDUKCIO/III%20fejezet.pdf]http://www.math.ubbcluj.ro/~andrasz/CD/INDUKCIO/III%20fejezet.pdf[/url][/size][url=http://www.math.ubbcluj.ro/~andrasz/CD/INDUKCIO/III%20fejezet.pdf][/url][/*][*][size=85]Pólya György: Indukció és analógia (Gondolat kiadó 1988. 60. oldal)[/size][/*][/list]
– Tarcsay Tamás

1.2.

–

1.3.

–

1.4.

–

1.5.

–

1.6.

–

1.7.

–

2.

Kombinatorika feladatok

  • 1. gyk_215 - Ismétléses kombinációs problémák
  • 2. Emelt érettségi 2022. május, 5.
  • 3. Emelt érettségi 2022. május, 8.
  • 4. Emelt érettségi 2021.október, 4.
  • 5. Emelt érettségi 2020. október, 2.
  • 6. Emelt érettségi 2020. október, 5.
  • 7. Emelt érettségi 2020. október, 9.
  • 8. Emelt érettségi 2022. október, 5.
  • 9. Emelt érettségi 2018. október, 5.
  • 10. Emelt érettségi 2018. május, 3.
  • 11. Emelt érettségi 2018. május, 5.
  • 12. Emelt érettségi 2017. október, 3.
  • 13. Emelt érettségi 2017. május, 8.
  • 14. Emelt érettségi 2016. október, 4.
  • 15. Emelt érettségi 2016. október, 6.
  • 16. Emelt érettségi 2016. október, 9.
  • 17. Emelt érettségi 2016. május, 2.
  • 18. Emelt érettségi 2016. május, 6.
  • 19. Emelt érettségi 2015. október, 4. b)
  • 20. Emelt érettségi 2015. október, 6.
  • 21. Emelt érettségi 2015. május, 3.
  • 22. Emelt érettségi 2015. május, 8.
  • 23. Emelt érettségi 2014. október, 6.
  • 24. Emelt érettségi 2014. október, 7.
  • 25. Emelt érettségi 2014. október, 8.
  • 26. Emelt érettségi 2014. május, 1.
  • 27. Emelt érettségi 2014. május, 9.
  • 28. Emelt érettségi 2013. május, 3.
  • 29. Emelt érettségi 2013. május, 8.
  • 30. Emelt érettségi 2012. október, 5.
  • 31. Emelt érettségi 2012. május, 6.
  • 32. Emelt érettségi 2011. október, 9.
  • 33. Emelt érettségi 2010. október, 6.
  • 34. Emelt érettségi 2010. október, 8.
  • 35. Emelt érettségi 2009. október, 5.
  • 36. Emelt érettségi 2009. október, 7.
  • 37. Emelt érettségi 2009. május, 9.
  • 38. Emelt érettségi 2008. október, 6.
  • 39. Emelt érettségi 2007. október, 8.
  • 40. Emelt érettségi 2007. május, 7.
  • 41. Emelt érettségi 2006. október, 2.
  • 42. Emelt érettségi 2006. február, 2.
  • 43. Emelt érettségi 2006. február, 7.
  • 44. Emelt érettségi 2005. október, 2.
  • 45. Emelt érettségi 2005. október, 8.
  • 46. Hány olyan metszéspontja van ...
  • 47. Hány rácspont ...
  • 48. Egy zárt ...
  • 49. Hány rácspont ... (3.)
  • 50. Hány olyan négyjegyű ...
  • 51. 2025. 122.
  • 52. 2025. 166.
  • 53. 2025. 186.
  • 54. 2025. 188.
  • 55. 2025. 189.
  • 56. 2025. 227.
  • 57. 2026. 48.
  • 58. 2026. 77.
  • 59. 2026. 101.
  • 60. 2026. 107.
  • 61. 2026. 110.
  • 62. 2026. 129.
  • 63. 2026. 133.

2.1.

gyk_215 - Ismétléses kombinációs problémák

[size=85]Kérdés: [url=https://www.gyakorikerdesek.hu/kozoktatas-tanfolyamok__hazifeladat-kerdesek__10843564-matekban-segitseg]https://www.gyakorikerdesek.hu/kozoktatas-tanfolyamok__hazifeladat-kerdesek__10843564-matekban-segitseg[/url][/size]
– Tarcsay Tamás

2.2.

–

2.3.

–

2.4.

–

2.5.

–

2.6.

–

2.7.

–

2.8.

–

2.9.

–

2.10.

–

2.11.

–

2.12.

–

2.13.

–

2.14.

–

2.15.

–

2.16.

–

2.17.

–

2.18.

–

2.19.

–

2.20.

–

2.21.

–

2.22.

–

2.23.

–

2.24.

–

2.25.

–

2.26.

–

2.27.

–

2.28.

–

2.29.

–

2.30.

–

2.31.

–

2.32.

–

2.33.

–

2.34.

–

2.35.

–

2.36.

–

2.37.

–

2.38.

–

2.39.

–

2.40.

–

2.41.

–

2.42.

–

2.43.

–

2.44.

–

2.45.

–

2.46.

–

2.47.

–

2.48.

–

2.49.

–

2.50.

–

2.51.

–

2.52.

–

2.53.

–

2.54.

–

2.55.

–

2.56.

–

2.57.

–

2.58.

–

2.59.

–

2.60.

–

2.61.

–

2.62.

–

2.63.

–

Information