olymmath

IL-GROSSMAN 2022 Problem 2

    We call a sequence of length nn of zeros and ones a "string of length nn " and the elements of the same sequence "bits". Let m,nm,n be two positive integers so that m<2nm<2^n . Arik holds mm strings of length nn . Giora wants to find a new string of length nn different from all those Arik holds. For this Giora may ask Arik questions of the form:

    "What is the value of bit number ii in string number jj ?"

    where 1≤i≤n1\leq i\leq n and 1≤j≤m1\leq j\leq m . What is the smallest number of questions needed for Giora to complete his task when:a) m=nm=n ?b) m=n+1m=n+1 ?

    Dataset text AI-MO AoPS. Quoted with source.

    Solutions

    No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

    Add a solution

    Similar problems

    These problems have the most words in common with this statement.

    Locator il-grossman/2022/p2 · Tag G4YS9AD550 · Edit this page on GitHub · Keys: j next, k previous