17
$\begingroup$

There is $5$x$5$ equidistance matrix dot given as below;

enter image description here

You need to remove dots from the figure where it will be impossible to form a square by drawing lines between dots at the end.

So what is the least number of dots you need to remove where forming a square by drawing lines between dots will be impossible?

Clarification: Dots need to be vertices of a square.

$\endgroup$
  • 2
    $\begingroup$ I interpreted this as "impossible to pick four dots that form a square", is this what is intended? (The way the puzzle is now written, it would also be possible to pick 8 points, and connect them pairwise with 4 lines that intersect so that the lines form a square) $\endgroup$ – Bass Aug 1 at 15:05
  • $\begingroup$ I'd like to point out that this is a special case of the hitting set problem, which is known to be NP-complete in general $\endgroup$ – Agnishom Chattopadhyay Aug 2 at 15:19
  • $\begingroup$ How many dots am allowed to removed??? I may remove all the dots, or I may remove all the dots except 2 or 3. Wont that be too easy??? $\endgroup$ – Always Confused Sep 8 at 7:26
12
$\begingroup$

Here's one with 10 dots removed. I tried for a long time to find one with 9, but I didn't succeed.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ fwiw, I wrote a python script to iterate through all possible combinations of dots and check for all the squares, and it agrees that the minimum number of dots is 10. There are 636 of those, out of 33554432 total possible squares, or 0.001895%. $\endgroup$ – IronEagle Aug 2 at 1:48
  • 1
    $\begingroup$ @IronEagle 636? I got less, my number is odd though, so I'm almost sure it's wrong, can you post a list of all your answers somewhere? gist or pastebin - so that I can find one that I did not find and correct my mistake. $\endgroup$ – Andrew Savinykh Aug 2 at 1:57
  • $\begingroup$ @Andrew Savinykh I can, although it might not be that human-readable. I used a 25-element list to represent the grid (right to left, top to bottom. 0 at the top left, 4 at the top right, etc.). Each grid that I tested is represented in binary (so grid #1 just has a dot in the top left, #16 has one in the top right, etc.). Pastebin link to code and list of answers: pastebin.com/JMTg1P4x Answer interpretation: 0's are missing dots, 1's are the dots that are left. Perhaps I missed a square position. I also don't account for rotationally identical or symmetrical answers. $\endgroup$ – IronEagle Aug 2 at 2:37
  • $\begingroup$ @IronEagle thank you, found my mistake. $\endgroup$ – Andrew Savinykh Aug 2 at 6:12
6
$\begingroup$

Here's an answer with the removal of

$11$ dots

Answer

enter image description here

If we interpret the question as Bass did, then I think we can remove

$13$ dots

Answer to Bass' version

enter image description here

$\endgroup$
  • $\begingroup$ row 4 col 3 could be added back, no? $\endgroup$ – jafe Aug 1 at 15:52
  • $\begingroup$ @jafe I was answering the question as clarified by Bass. If we add this point back then the horizontal and vertical lines through it are achievable which together with the horizontal and vertical lines through point (2,5) would form a square. $\endgroup$ – hexomino Aug 1 at 15:55
  • $\begingroup$ @jafe Oray had commented confirming Bass' assumption but has since deleted the comment. $\endgroup$ – hexomino Aug 1 at 15:55
  • $\begingroup$ this is a valid answer, but not the least number of dots to remove. $\endgroup$ – Oray Aug 1 at 16:15
  • $\begingroup$ @Oray Is Bass' interpretation correct? $\endgroup$ – hexomino Aug 1 at 16:19
5
$\begingroup$

Since I cannot post pictures in a comment, here's my question in clearer terms:

Did I form a square by drawing lines between dots? (I know I did. Does it count, though?)

enter image description here

(For better visibility, I deviated from the apparent standard of using near-imperceptible shade changes, and marked the relevant dots with bell peppers instead.)

$\endgroup$
  • 3
    $\begingroup$ I see your point with some peppers :D I put a clarification for that :) AS "dots need to be vertices of a square." but good point though. $\endgroup$ – Oray Aug 1 at 16:29
0
$\begingroup$

I tried it with 9 dots removed.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ There's a diagonal square with vertices C1,D3, B4, A2 $\endgroup$ – StephenTG Aug 2 at 13:10
  • $\begingroup$ B4 is deleted though. $\endgroup$ – blanche_chat Aug 2 at 13:12
  • $\begingroup$ I realize now that my notation has the order of numbers reversed from chess notation. I was assuming A-E indicating columns going left to right, 1-5 indicating rows from top to bottom $\endgroup$ – StephenTG Aug 2 at 13:22
  • 1
    $\begingroup$ But I found another diagonal square on B3 D2 E4 C5 (or C2 B4 D5 E3) depending on how you see it. $\endgroup$ – blanche_chat Aug 2 at 13:23
0
$\begingroup$

I have an attempt with 9 dots. It looks like the minimum is 10, but I can't find my mistake. Is there a square here I'm missing?

enter image description here

$\endgroup$
  • $\begingroup$ yes there is one square exist A4-B1-E2-D5 $\endgroup$ – Oray Aug 2 at 14:21
  • $\begingroup$ Oray, good catch, I didn't think to look for that type of square. $\endgroup$ – makajawan Aug 2 at 14:32
  • $\begingroup$ I see four of them: A4-B1-E2-D5, A2-D1-E4-B5, A2-C2-C4-A4, and C2-E2-E4-C4. $\endgroup$ – plasticinsect Aug 2 at 16:42

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.