Math Puzzle: Area of Concentric Rings

Question

The problem below appeared on the latest round of Google Code Jam:

---

Maria has been hired by the Ghastly Chemicals Junkies (GCJ) company to help them manufacture bullseyes. A bullseye consists of a number of concentric rings (rings that are centered at the same point), and it usually represents an archery target. GCJ is interested in manufacturing black-and-white bullseyes.

Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm. Then she repeats the following process for as long as she has enough paint to do so:

Maria imagines a white ring of thickness 1cm around the last black ring. Then she draws a new black ring of thickness 1cm around that white ring. Note that each "white ring" is simply the space between two black rings. The area of a disk with radius 1cm is π cm2. One millilitre of paint is required to cover area π cm2. What is the maximum number of black rings that Maria can draw? Please note that:

• Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.
• There will always be enough paint to draw at least one black ring.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a line containing two space separated integers: r and t.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of black rings that Maria can draw.

**Sample Input**    
5
1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000


**Sample Output**  
Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49

---

The inputs were very large, so a brute force approach wouldn't solve it in time. I looked at the top solutions, and most used a variation of the formula below:

2*R*X + (2*X-1)*X <= T

where R is the radius of the first white circle, X is the total number of rings she can paint, and T is the milliliters of ink she has available. To find the answer you would basically do a binary search looking for the highest X that would make the equation true.

My question: Where does that formula come from? Is it possible to explain how come this solves the problem, in simple terms? Any light you can shed will be appreciated.

Answer 1

The annulus with radii $r_1<r_2$ has area $\pi(r_2^2-r_1^2)$. So it requires $r_2^2-r_1^2$ milliliters of paint. When $r_2-r_1=1$, we have that $r_2^2-r_1^2=(r_2-r_1)(r_2+r_1)=r_2+r_1=2r_1+1$.

Now, if your $n$th black strip is an annulus with radii $r_1(n)=r+2(n-1)$ and $r_2(n)=r_1(n)+1$, and the paint required is $$2r_1(n) +1= 2r + 1 + 4(n-1)$$

So, after $M$ stripes, she will have used up:

$$\sum_{n=1}^M \left(2r+1+4(n-1)\right)=(2r+1)M + 4\frac{M(M-1)}{2}=2rM + M(2M-1)$$

Also, a binary search isn't necessary. You can just solve the equation:

$$2x^2+(2r-1)x-T=0$$ and take the largest integer less than the larger root. That larger root is:

$$\frac{1-2r+\sqrt{(2r-1)^2+8T}}{4}$$

Answer 2

If the inner radius of a ring is $r$ and the outer radius is $r+1$, the area of the ring is $\pi(r+1)^2-\pi r^2=\pi (2r+1)$, so the ring takes $2r+1$ milliliters of paint. The next ring is $2$cm greater in radius (one black, one white), so takes 2(r+2)+1 milliliters. To paint $x$ rings starting at $r$ takes $2r+1+2(r+2)+1+2(r+4)+1+\ldots 2(r+2x-2)+1=\sum_{i=0}^{x-1}(2r+4i+1)=2rx+2x(x-1)+x=2rx+2x^2-x$

Then you don't need to do a binary search. You can just solve the quadratic for $x$ and round down.