\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=3pt
\centerline{\bf Keres\'esi feladatok}
 
\bigskip
 
Olyan probl\'em\'akkal foglalkozunk, amikor egy
adathalmazban meg kell keresni a legnagyobb, legkisebb, m\'asodik
legnagyobb, stb.\ elemet. F\H o c\'elunk {\it als\'o}\/ becsl\'esek
keres\'ese. Egy tipikus eredm\'eny a k\"ovetkez\H o:
 
\smallskip  \noindent
A minim\'alis \'es maxim\'alis elem egy\"uttes
megkeres\'es\'ehez $n$ elem k\"oz\"ul  legal\'abb $\dfrac{3n}2-2$
\"osszehasonl\'{\i}t\'as kell, \smallskip
 
\'Erintj\"uk $n$ elem rendez\'es\'ehez sz\"uks\'eges m\H uveletek
sz\'am\'ara vonatkoz\'o becs\-l\'est, \'es azt a meglep\H o eredm\'enyt
is, hogy $n$ elemet lehet $O\left(\dfrac{n\log n}{ \log\log n}\right)$
m\H uvelettel
is rendezni. Ha marad id\H o, az al\'abbi feladatot is megoldjuk:
 
\bigskip
Egy matematikai kongresszuson 200 k\"uld\"ott vesz r\'eszt,
ezek mindegyike
vagy \H or\"ult vagy norm\'alis. A norm\'alis matematikusok mindig
igazat mondanak, az \H or\"ultek meg\-b\'{\i}z\-ha\-tat\-lanok:
v\'alaszuk lehet
igaz is \'es hamis is. A r\'esztvev\H ok t\"obbs\'ege norm\'alis. Egy
\'ujs\'ag\'{\i}r\'onak meg kell tudnia, hogy kik a norm\'alisok. E
c\'elb\'ol
b\'arkihez odamehet \'es megk\'erdezheti r\'amutatva valaki m\'asra:
``\H O norm\'alis vagy \H or\"ult?'' V\'alaszt mindig kap, \'es ennek
igazs\'aga att\'ol f\"ugg, hogy a k\'erdezett norm\'alis-e vagy sem.
 
H\'any k\'erd\'est kell feltennie ahhoz, hogy mindent megtudjon?
 
Mutassuk meg, hogy ha $n$ r\'esztvev\H o van, \'es a t\"obbs\'eg norm\'alis,
akkor
konstans$\,\times n$ k\'erd\'es elegend\H o ehhez. Ha ugyanannyi a
norm\'alis \'es az
\H or\"ult r\'esztvev\H ok sz\'ama, akkor lehetetlen ak\'arh\'any k\'erd\'es
seg\'\i{}ts\'eg\'evel biztosan
kider\'\i{}teni az igazs\'agot. Annak pontos meghat\'atoz\'asa, hogy
h\'any k\'erd\'es
kell legal\'abb a helyzet tiszt\'az\'as\'ahoz, (ha t\"obb a norm\'alis
mint az \H or\"ult), l\'enyegesen nehezebb, de megoldhat\'o probl\'ema.
 
\bigskip
\rightline {Csirmaz L\'aszl\'o \qquad\qquad}
 
\medskip
\centerline{\bf Feladatok}
\medskip
 
\item{1.} Egy kies\'eses versenyben  $n$ r\'esztvev\H o k\"oz\"ul
eld\"ontik, hogy ki a {\it harmadik}\/ legjobb. H\'any m\'er\-k\H
o\-z\'es\-re
ker\"ul sor? \'Es ha a $k$-adik legjobbra vagyunk kiv\'ancsiak?
 
\item{2.} A k\"ovetkez\H o algoritmus kiv\'alasztja a legnagyobb
\'es a m\'asodik legnagyobb \'ert\'eket $L[1], \dots, L[n]$ k\"oz\"ul.
H\'any \"osszehasonl\'{\i}t\'ast v\'egez a legrosszabb esetben, illetve
\'atlagosan?
 
{\narrower
     $\text{max:}=\max\{L[1],L[2]\}$;\par
     $\text{second:}=\min\{L[1],L[2]\}$;\par
     $\;\;\;\;\;\;\text{\bf for\ }i:=3\text{\bf\ to\ }n\text{\bf\ do
      }$\par
     $\;\;\;\;\;\;\text{\bf if }L[i]>\text{second }\text{\bf then }$\par
     $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{\bf\ if } L[i]>\text{max }
      \text{\bf then }\text{second:}=\text{max};\; \text{max:}
       =L[i];$\par
     $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{\bf\ else }
         \text{second:}=L[i];$\par}
 
\item{3.} Mutassuk meg, hogy 5 elem k\"oz\"ul a k\"oz\'eps\H ot 6
\"osszehasonl\'{\i}t\'assal mindig ki lehet v\'alasztani.
 
\item{4.} $n$ elem k\"oz\"ul a 10 legkisebb b\'armelyike j\'o. H\'any
\"osszehasonl\'{\i}t\'assal tudunk egy ilyet tal\'alni?
 
\item{5.} Az $M$ $n\times n$ m\'atrix minden sor\'aban az elemek
cs\"okkennek, \'es minden oszlop\'aban az elemek szint\'en cs\"okkennek.
Meg kell \'allap\'{\i}tanunk, hogy egy $x$ sz\'am szerepel-e a
m\'atrixban.
Egy l\'ep\'esben $x$-et \"osszevethetj\"uk $M$ tetsz\H oleges elem\'evel,
\'es meg\-kap\-juk, hogy egyenl\H o, kisebb vagy nagyobb-e n\'ala.
H\'any l\'ep\'est kell tenn\"unk?
 
\item{6.} Egy \'utkeresztez\H od\'eshez \'er\"unk, ahol az egyik \'ut
a pokolba a m\'asik pedig a paradi\-csomba vezet. Az \'uton h\'arom
ikertestv\'er \'all, akik minden igen vagy nemmel megv\'alaszolhat\'o
k\'erd\'esre v\'alaszolnak. Egyik\"uk mindig igazat mond, a m\'asodik
mindig hazudik. A harmadik testv\'er s\"uket, de ezt titkolja, azaz
mindig v\'alaszol valahogy a k\'erd\'est\H ol teljesen f\"uggetlen\"ul.
\'Allap\'{\i}tsuk meg k\'et k\'erd\'es seg\'{\i}ts\'eg\'evel azt, hogy
melyik \'ut vezet a paradicsomba.
 
\bye