Skip to content

Grid shading that forces a crowded row

Question

A grid of white unit squares has rr rows and cc columns. In every column exactly ss squares are coloured black. Find the smallest cc, as a function f(r,t,s)f(r,t,s), that guarantees some row contains at least tt black squares, and evaluate f(30,21,14)f(30,21,14).

Short answer

43. If every row had at most t−1t-1 black squares the total would be at most r(t−1)r(t-1), while the total is cscs; and a cyclic shading spreads squares evenly so that cs≤r(t−1)cs\le r(t-1) is achievable. Hence f=⌊r(t−1)/s⌋+1=⌊600/14⌋+1=43f=\lfloor r(t-1)/s\rfloor+1=\lfloor 600/14\rfloor+1=43.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free