What is the minimum number of touches for painting at least a $100*100$ rectangle if you have one circular stamp tool that paints a circular area of $1$ unit radius in every touch?

This question is very similar to Paint the rectangle with least movement. But this time there is no brush tool for painting.


If you array circles with radius = 1 on a triangular as shown below, you can cover a rectangular area with

 height = (3n-1)/2, where n is the number of rows of circles, and

 width = sqrt(3)(2m-1)/2, if each row is of length m, or
 width = sqrt(3)(m-1), if alternate rows are of length m, and m-1 

So you can cover a 100x100 square with 67 rows, of alternating length 59,58,59...(actual rectangular area covered is 100 high by ~100.459 wide).

Total number of circles used is 34x59 + 33*58 = 3920

enter image description here

  • $\begingroup$ that totally sounds reasonable!! $\endgroup$ – Martin Frank Oct 9 '14 at 4:02
  • 1
    $\begingroup$ If you start with a 58-row, the total number of circles used would be 34x58 + 33x59 = 3919. $\endgroup$ – Florian F Oct 9 '14 at 15:43

you might need w/2 x h/2 filled circles (even filled circles) on the first run and then need (w-1)/2 x (h-1)/2 filled circles (odd filled circles) to fill the gaps between... you can 'cut' pathes when you draw a even line and then switch to an odd line...

lenght of even line = 100; length of odd line = 99; path to switch from odd to even (and back) = Math.Squrt(2) (i'll say it's 1.4 for terms of easier use)...

so you have 100 x 100 + 99 x 99 + 99*1.4 = 10'000 + 9801 + 138.6 = 19939.6 (having rounding erros)

enter image description here

BLACK  = even circles
RED    = odd circles
PURPLE = rectangle
GREEN  = path

i can't proof that this path would be shorter:

enter image description here

  • $\begingroup$ your second path (or solution) was shorter. but the question still stays unanswered, "what is the minimum number?" $\endgroup$ – Rafe Oct 8 '14 at 18:30
  • $\begingroup$ I have [somehow] copied your answer up here $\endgroup$ – Rafe Oct 8 '14 at 18:35
  • $\begingroup$ wow thank you @Rafe - i hope this will be a good start for discussion whereas i must confess the solution from penguino looks very nice as well... $\endgroup$ – Martin Frank Oct 9 '14 at 4:01
  • $\begingroup$ There's no "paths" involved here, just numbers of circles. The second half of the first picture and the second picture can be removed, and as Rafe mentioned, there is no circle count. $\endgroup$ – TheRubberDuck Oct 9 '14 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.