3. Zadatak

Pokazat ćemo da najviše $\left\lfloor\frac{n+1}{2}\right\rfloor$ rečenica može biti istinito, tj. za paran broj $n=2m$ najviše $m=\frac12n$, a za neparan $n=2m-1$ najviše $m=\frac{n+1}{2}$. Kartica na kojoj piše “Barem $k$ rečenica lijevo od ove kartice je lažno” nazivamo “kartica $k$”. Također, reći ćemo “kartica $k$ je lažna (istinita)” umjesto “rečenica na kartici $k$ je lažna (istinita)”.

Ako kartice poredamo redom: $0,n-1,1,n-2,2,\ldots$ onda su rečenice na prvoj, trećoj, petoj,$\ldots$ po redu istinite, a na ostalim karticama lažne. U tom rasporedu točno je $\left\lfloor\frac{n+1}{2}\right\rfloor$ istinitih kartica.

Dokažimo sada da ne može više od $\left\lfloor\frac{n+1}{2}\right\rfloor$ kartica biti istinito. Neka je $n=2m$ ili $n=2m-1$. Ako je kartica $k$ za neki $k\ge m$ istinita, onda ima barem $k$ lažnih kartica (već i među onima lijevo od nje). To znači da ima najmanje $m$ lažnih, odnosno najviše $n-m\le m$ istinitih kartica. U suprotnom, sve su kartice za $k>m$ lažne, pa ima najviše $m$ istinitih kartica.