[ZK] 16.6.2005

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.

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...