3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ that totally sounds reasonable!! $\endgroup$
    – Martin Frank
    Commented Oct 9, 2014 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
    Commented Oct 9, 2014 at 15:43
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ your second path (or solution) was shorter. but the question still stays unanswered, "what is the minimum number?" $\endgroup$
    – Rafe
    Commented Oct 8, 2014 at 18:30
  • $\begingroup$ I have [somehow] copied your answer up here $\endgroup$
    – Rafe
    Commented Oct 8, 2014 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
    Commented Oct 9, 2014 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
    Commented Oct 9, 2014 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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