MathDB

We call a sequence of length

n

of zeros and ones a "string of length

n

" and the elements of the same sequence "bits". Let

m,n

be two positive integers so that

m<2^n

. Arik holds

m

strings of length

n

. Giora wants to find a new string of length

n

different from all those Arik holds. For this Giora may ask Arik questions of the form:
"What is the value of bit number

i

in string number

j

?"
where

1\leq i\leq n

and

1\leq j\leq m

. What is the smallest number of questions needed for Giora to complete his task when: a)

m=n

? b)

m=n+1

P2