# Paint the Rectangle with least number of Circular Stamp Touches

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.

## 2 Answers

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 • that totally sounds reasonable!! – Martin Frank Oct 9 '14 at 4:02
• If you start with a 58-row, the total number of circles used would be 34x58 + 33x59 = 3919. – 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) BLACK  = even circles
RED    = odd circles
PURPLE = rectangle
GREEN  = path


i can't proof that this path would be shorter: • your second path (or solution) was shorter. but the question still stays unanswered, "what is the minimum number?" – Rafe Oct 8 '14 at 18:30
• I have [somehow] copied your answer up here – Rafe Oct 8 '14 at 18:35
• 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... – Martin Frank Oct 9 '14 at 4:01
• 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. – TheRubberDuck Oct 9 '14 at 17:20
{"ft_lang_label":"__label__en","ft_lang_prob":0.94845206,"math_prob":0.9832797,"size":305,"snap":"2019-35-2019-39","text_gpt3_token_len":64,"char_repetition_ratio":0.11295681,"word_repetition_ratio":0.0,"special_character_ratio":0.2262295,"punctuation_ratio":0.050847456,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9924371,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,9,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-08-20T01:43:06Z\",\"WARC-Record-ID\":\"<urn:uuid:f8feb898-6e76-442c-a71d-59357976c931>\",\"Content-Length\":\"145652\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ba2f2794-0bb5-43cf-882c-82a0f98eddef>\",\"WARC-Concurrent-To\":\"<urn:uuid:e3de104c-9df0-4d4d-9fbb-55182d9c49a3>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://puzzling.stackexchange.com/questions/2675/paint-the-rectangle-with-least-number-of-circular-stamp-touches?noredirect=1\",\"WARC-Payload-Digest\":\"sha1:7I42FOXMQ7QCNL3X5WHQFAIKLSAHNH4B\",\"WARC-Block-Digest\":\"sha1:S6W46NLDT23PJBWIR3S6E5QDA4AONI57\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-35/CC-MAIN-2019-35_segments_1566027315174.57_warc_CC-MAIN-20190820003509-20190820025509-00430.warc.gz\"}"}