# [ZK] 16.6.2005

<{ForumPost(poster="MyS", timestamp=2005-06-16 15:56:15)}>
Cerstve zpravy z bitevniho pole. Na vsechny se dostane...  
1) Dokazat theta pro T(n)=T(n/2)+2*T(n/3)+n^2  
2) Dan souvisly neorientovany graf. Vsechny hrany maji unikatni vahy. Plati, ze mnozina vsech hran, ktere jsou lehke pro nejaky rez, je kostra?  
3) Dana tabulka men a smennych kurzu, kazda usp. dvojice je jen 1x. Tj. A-KURZ-B znamena, ze za 1 Acko dostanu KURZ Becek. Je mozne dosahnout zisku tak, ze zacnu s nejakou menou, smenuju a smenuju, skoncim u te, u ktere jsem zacal, a mam vic, nez jsem mel na pocatku? Napoveda: uzijte logaritmy.  
  
Mno, a nejaky tipy od desatnika MySe...nectete, pokud si chcete resit:-). Ja vas varoval.... tak treba ta 2) narozdil od vcerejska pri tomto predpokladu navic formulaci plati (ja dokazoval bezkruznicovitost indukci podle velikosti jedne z komponent rezu, ale za postup nerucim...tak proc to sem vlastne pisu...). Mno, a ve trojce staci vtipne uzit logaritmy a pak hledat v grafu zap. cykly. Konec hlaseni.
<{/ForumPost}>

<{ForumPost(poster="macbeth", timestamp=2005-06-17 16:20:19)}>
ja len doplnim, ze prve bolo n^2, vyslo to pekne,   
druhe stacilo ukazat, ze bud hrany kruznice nekrizia rez a v tom pripade nas to nezaujima, pretoze nemozem vybrat ziadnu hranu z kruznice a ak nejaka hrana krizi rez, tak urcite existuje na tej kruznici este ina hrana, ktora krizi dany rez, a tak tu najtazsiu hranu na reze nie je mozne vybrat...  
trojka, nejak tak, bolo treba hladat zaporne cykly...
<{/ForumPost}>