algebra-precalculusgeometry
What is the diameter of the largest circle that can be drawn on a
chessboard so that its entire circumference gets covered by the black
squares and no part of the circumference falls on any white
space, given that the chessboard has black and white squares of size one
inch.
I am looking forward to some ideas/hints for this problem.
Let's analyze a single case:
If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.
So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$
So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$
If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$
Let's now recall the formulas we had.
We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.
A better method:
Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that $$a=x/p_x$$ where $a$ is the value of the actual side of our squares. Then we know that for our side to fit we need to reduce it: $$S_x=y/(\lceil y/a \rceil)$$ We do the same with $S_y$ and calculate $max(S_x,S_y)$ The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.
Plain, unoptimized C Code
Some multiplications may be reused but for code readability and practical uses this is enough. Input: values of $x$,$y$, and $n$. Handcoded.
Output: The optimal side of our squares
#include <math.h>
#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int main(){
double x=5, y=6, n=7;//values here
double px=ceil(sqrt(n*x/y));
double sx,sy;
if(floor(px*y/x)*px<n) //does not fit, y/(x/px)=px*y/x
sx=y/ceil(px*y/x);
else
sx= x/px;
double py=ceil(sqrt(n*y/x));
if(floor(py*x/y)*py<n) //does not fit
sy=x/ceil(x*py/y);
else
sy=y/py;
printf("%f",MAX(sx,sy));
return 0;
}
The side lengths of the highlighted triangle are $1$, $\sqrt{2^2+\left(\frac{3}{2}\right)^2}$ and $\sqrt{2^2+\left(\frac{1}{2}\right)^2}$ by the Pythagorean theorem. Since its area is $1$, we have: $$ \color{red}{R} = \frac{abc}{4\Delta} = \frac{1}{4}\sqrt{1\cdot\frac{25}{4}\cdot\frac{17}{4} }=\color{red}{\frac{5}{16}\sqrt{17}}\approx 1.28847. $$
Best Answer
There are two solutions.
It helps to draw a diagram like this:
or this:
I don't think any bigger would fit. But how do you prove this statement???