A grid and a shape

[Genady]

Imagine points on a plane which are vertices of a square 1x1 grid covering the entire plane.

Find a shape with area < 1 such that it cannot be placed on the plane without touching at least one of these points.  

[Genady]

OK then. Consider the other challenge: prove that it is impossible.

IOW, prove that any shape with area <1 can be placed on the plane without touching the grid.

[TheVat]

Not clear on definition of shape, e.g. any n-gon?  Or literally any shape that's an enclosed space?    Does it count as touching only  on the perimeter, or must the shape not be around a point?

Are fractals involved?

[Genady]

8 minutes ago, TheVat said:

Not clear on definition of shape, e.g. any n-gon?  Or literally any shape that's an enclosed space?    Does it count as touching only  on the perimeter, or must the shape not be around a point?

Are fractals involved?

Literally any shape.

Should not touch / cover / contain any points of the grid. IOW, all parts of the shape are between the points of the grid = all points of the grid are outside of the shape.

Any shape with a definite area is allowed. The only limitation is that its area is less than unity.

[Genady]

Think the other way around, invert the problem.

Imagine a shape on a plane and look for a way to place the grid onto it without touching the shape.

[TheVat]

 

Thanks, that was sort of how I was looking at it.  It seems like this

Spoiler

A star polygon would satisfy the OP challenge.  A pentagram seemed to work, though I rushed through the process, because we are packing to leave town for a few days.

might work.  

[Genady]

2 minutes ago, TheVat said:

 

Thanks, that was sort of how I was looking at it.  It seems like this

  Hide contents

A star polygon would satisfy the OP challenge.  A pentagram seemed to work, though I rushed through the process, because we are packing to leave town for a few days.

might work.  

OK, but imagine an arbitrary shape on a plane, an inkblot or even several inkblots (the shape doesn't have to be one connected piece) ...

[md65536]

On 3/7/2023 at 7:15 AM, Genady said:

Find a shape with area < 1 such that it cannot be placed on the plane without touching at least one of these points.  

 

Spoiler

I'm thinking of a very thin very long and very slight curve that gradually increases in curvature, so that for a given length L, every possible length n*L for some integer n, where n*L is less than the length of the shape ... ??? can be found on the shape no matter how it's oriented. I'm not sure if that's the right criteria. Then if it works for all L in [1, sqrt(2)], it should touch at least one point. Is this on the right track? I feel like I got it backwards, and I'm missing something involving the width of the shape.

We're trying to prove 2 opposite things. Does trying to prove that an arbitrary shape can be placed without touching a point, lead to a contradiction?

 

Edited May 2, 2023 by md65536

[Genady]

3 minutes ago, md65536 said:

We're trying to prove 2 opposite things.

The original goal has been inverted a few posts up. Now we try to prove this:

 

4 minutes ago, md65536 said:

that an arbitrary shape can be placed without touching a point

Of course, it is either one or another, i.e., either there exists a shape that cannot be placed without touching or any shape can be placed without touching. But I have already hinted that the latter is correct. 

[md65536]

48 minutes ago, Genady said:

But I have already hinted that the latter is correct. 

No fair asking for something that's impossible in the original problem 😠

"Proof":

Spoiler

Assume there's a shape with area <1 that touches any 1x1 grid, placed on the plane. Place down all possible grids of the same orientation, so that the plane is completely covered. Consider the square from (0,0) to (1,1), with size 1. For all grids, if that grid touches the shape, remove all points on the grid, also removing the point from the square.

When done, if you haven't removed all the grids then the assumption was wrong, and there is a grid that doesn't touch the shape. If you've removed all the grids, you've removed at least one point from the shape for every point in the square you removed, so you removed at least an area of 1 from the shape, and the shape must have had an area of at least 1.

I think there might be a problem here talking about the area of points, like with the Banach-Tarski paradox.

Edited May 2, 2023 by md65536

[Genady]

4 hours ago, md65536 said:

No fair asking for something that's impossible in the original problem

It depends on the culture, I guess. In my school, when we were given an equation to solve, there was always a possibility that the equation does not have a solution, in which case we were expected to prove that it is so.

 

5 hours ago, md65536 said:

"Proof":

  Reveal hidden contents

Assume there's a shape with area <1 that touches any 1x1 grid, placed on the plane. Place down all possible grids of the same orientation, so that the plane is completely covered. Consider the square from (0,0) to (1,1), with size 1. For all grids, if that grid touches the shape, remove all points on the grid, also removing the point from the square.

When done, if you haven't removed all the grids then the assumption was wrong, and there is a grid that doesn't touch the shape. If you've removed all the grids, you've removed at least one point from the shape for every point in the square you removed, so you removed at least an area of 1 from the shape, and the shape must have had an area of at least 1.

I think there might be a problem here talking about the area of points, like with the Banach-Tarski paradox.

The idea of your proof is right and the proof is very close, except the issue you've mentioned about the area covered by the points. This issue can be eliminated by a modification of the proof where instead of removing points from a 1x1 square we find where to put a point. (I hope this last hint helps rather than distracts.)

+1

[MonDie]

Nothing, if it can rotate.
Oh, just delete this. I had two proofs.Everything after the first *spoiler* bracket disappeared. I'm running NoScript on Ubuntu Firefox.

[md65536]

20 hours ago, Genady said:

instead of removing points from a 1x1 square we find where to put a point.

 

Spoiler

I feel like I'm missing something simpler than this:

 

Say you have any shape of area < 1. Make a new shape by cutting the entire plane into 1x1 tiles with cuts along whole values of x and y, then overlapping all tiles and their pieces of the original shape, with a corner at (0, 0). Since the total area < 1, there must be some point inside that 1x1 tile that isn't covered by the new shape, and if you move both shapes together (without rotation) so that such a point is on a grid vertex, then neither shape is touching the grid.

 

Intuition is that rotation will complicate things because it allows for more ways in which a shape can be moved to dodge the grid, but it seems not to matter because it can still be placed off the grid without rotation.

Edited May 3, 2023 by md65536

[Commander]

[Genady]

2 hours ago, md65536 said:

 

  Hide contents

I feel like I'm missing something simpler than this:

 

Say you have any shape of area < 1. Make a new shape by cutting the entire plane into 1x1 tiles with cuts along whole values of x and y, then overlapping all tiles and their pieces of the original shape, with a corner at (0, 0). Since the total area < 1, there must be some point inside that 1x1 tile that isn't covered by the new shape, and if you move both shapes together (without rotation) so that such a point is on a grid vertex, then neither shape is touching the grid.

 

Intuition is that rotation will complicate things because it allows for more ways in which a shape can be moved to dodge the grid, but it seems not to matter because it can still be placed off the grid without rotation.

You are right. +1

Here is my take:

Spoiler

Take a plane without a grid on it. Place the shape on it arbitrarily. Cut the plane with the shape on it into 1x1 squares. "Stack" all the squares on top of each other to get one 1x1 square from all the original squares overlapped. As you said, since the total area of the shape <1, the overlapping parts of the original shape do not cover the entire 1x1 square. Some part of the square remains uncovered. Mark any point in this part through the entire stack, i.e., the same point on each of the overlapping squares. Return all the squares to their original positions. We get the plane with the original shape on it and with all the marked points making a 1x1 grid. Now we can shift and rotate this plane to align this grid with the original grid and we get the original shape placed without touching the original grid.

 

[Genady]

5 hours ago, Commander said:

Any comment? Question?

[studiot]

On 3/7/2023 at 2:15 PM, Genady said:

Imagine points on a plane which are vertices of a square 1x1 grid covering the entire plane.

Find a shape with area < 1 such that it cannot be placed on the plane without touching at least one of these points.  

The rules are not clear to me.

Do you mean that the shape must not cross any of the gridlines that the blue points form the intersection points of ?

Or do you mean not intersect any of the points themselves ?

 

Incidentally the solution to the problem of not crossing any gridlines is explored quite deeply in structural chemistry and mineralogy

[Genady]

Just now, studiot said:

The rules are not clear to me.

Do you mean that the shape must not cross any of the gridlines that the blue points form the intersection points of ?

Or do you mean not intersect any of the points themselves ?

 

Incidentally the solution to the problem of not crossing any gridlines is explored quite deeply in structural chemistry and mineralogy

Thank you for asking clarifying questions. There are no gridlines here, only the points, which are the intersection points of the 'imaginary' gridlines. The shape should not intersect any of these points.

BTW, to be sure, the OP question has been changed to this:

prove that any shape with area <1 can be placed on the plane without intersecting these points.

[studiot]

19 hours ago, Genady said:

Thank you for asking clarifying questions. There are no gridlines here, only the points, which are the intersection points of the 'imaginary' gridlines. The shape should not intersect any of these points.

BTW, to be sure, the OP question has been changed to this:

prove that any shape with area <1 can be placed on the plane without intersecting these points.

Thank You.

I can't therefore see the problem.

The blue dots constitute part of the plane.

The white areas constitute the rest of the plane and to satisfy you first condition (non intersection with the blue dots) the shape must lie entirely on the white area.

Any circle or disc, centered at the intersection of the diagonals between adjacent four blue dots of radius less than half the interdiagonal length will lie entirely on the white, between the four dots.

However you have also stated a second condition that the area has to be less than 1 area unit.

Since the larger circles and discs have a area greater than 1, we must slim down the acceptable range of radii to also being less than 1/square root (PI).

 

 

[Genady]

2 minutes ago, studiot said:

Thank You.

I can't therefore see the problem.

The blue dots constitute part of the plane.

The white areas constitute the rest of the plane and to satisfy you first condition (non intersection with the blue dots) the shape must lie entirely on the white area.

Any circle or disc, centered at the intersection of the diagonals between adjacent four blue dots of radius less than half the interdiagonal length will lie entirely on the white, between the four dots.

However you have also stated a second condition that the area has to be less than 1 area unit.

Since the larger circles and discs have a area greater than 1, we must slim down the acceptable range of radii to also being less than 1/square root (PI).

 

 

You have (correctly) shown that some shapes can be placed entirely on the white. However, the question is to show that any shape with area < 1 can be placed this way.

Quote

prove that any shape with area <1 can be placed on the plane without intersecting these points

Maybe I'm missing something in English here? Is the correct way to say this, "any given shape ..."?

Or "arbitrary shape"?

[Genady]

I thought of a way that might make this puzzle a bit more transparent (pun intended, see below).

You have a plane with the grid points on it as described in the OP. Somebody gives you a transparency with an inkblot on it. You position the transparency on top of your plane in such a way that the inkblot does not cover or touch any of the grid points. 

Prove that this positioning can be done for inkblot of any shape as long as its area is less than unity.

[Commander]

On 3/7/2023 at 7:45 PM, Genady said:

Imagine points on a plane which are vertices of a square 1x1 grid covering the entire plane.

Find a shape with area < 1 such that it cannot be placed on the plane without touching at least one of these points.  

Spoiler

We can not place a ring [a circle within a circle] of diameter more than 1 for the inner circle and the surface area such that it is less than 1  [ie. D1² - D²  is less than 4/Pi]

Spoiler

I hope this answers

 

Edited May 5, 2023 by Commander
correction

[Genady]

3 hours ago, Commander said:

  Hide contents

We can not place a ring [a circle within a circle] of diameter more than 1 for the inner circle and the surface area such that it is less than 1  [ie. D1² - D²  is less than 4/Pi]

  Reveal hidden contents

I hope this answers

 

Sorry, but we can:

[Commander]

I thought it shouldn't envelope like this

Edited May 6, 2023 by Commander

[Genady]

47 minutes ago, Commander said:

I thought it shouldn't envelope like this

OK, it's clearer now.