Нека kk и nn са фиксирани положителни цели числа. В играта на отгатване с лъжи Ейми избира цели числа xx и NN с 1xN1\le x\le N. Тя казва на Бен какво е NN, но не и какво е xx. След това Бен може многократно да пита Ейми дали xSx\in S за произволни множества SS от цели числа. Ейми винаги отговаря с „да“ или „не“, но може да лъже. Единственото ограничение е, че тя може да излъже най-много kk пъти поред. След като зададе колкото въпроси желае, Бен трябва да посочи множество от най-много nn положителни цели числа. Ако xx е в това множество, той печели; иначе губи. Докажете, че: а) ако n2kn\ge 2^k, Бен винаги може да спечели; б) за достатъчно големи kk съществува n1.99kn\ge 1.99^k, за което Бен не може да си гарантира победа.
📣НОВО: Добавени задачи от Международната олимпиада по математика 2000-2024
Още задачи при скрол