Can an Ink Stain Always Be Avoided with a 1 x 1 cm Net on Paper?

[haiha]

My friends gave me a problem that he said it can be very simple to be proved, but really it is not (to me)
There is an ink stain with area of smaller than 1cm2 on a sheet of paper. Prove that there is always possibility you can place a net with square mesh of 1 x 1 cm on the sheet so that not any knot point touches the ink stain.

 

[CRGreathouse]

I don't understand the question. What is a 'knot point'? How large is the paper?

It seems what you are trying to say something like: "For every piece of paper such that X, you can place a 1x1 square such that Y." Beyond that I'm not at all sure.

 

[haiha]

Thanks for your reply.
A 'knot point' is the crossing point of 2 any lines of the net. The sheet of paper and the net are considered infinitively large, and the ink stain also can be of any shape. The only constraint of the stain is that its area is smaller than 1 cm2.

 

[haiha]

Please, help !

One more clue : the ink stain can be several separate pieces, but total area must be smaller than 1 cm2

 

[Fredrik]

I've only been able to come up with a non-rigorous argument.

Imagine that the paper, the ink stain and the net are discrete rather than continuous, as if we're looking at a computer screen rather than paper. Suppose that the "pixels" that are 1/n cm across, so that there are n^2 pixels in each cm^2. Place the net so that two of the lines meet somewhere on the ink stain.

Now we make an assumption that we hope will lead to a contradiction: No matter where we move the net, two lines will cross somewhere on the ink stain.

There are only n^2-3 positions that you can move the net to that aren't equivalent to the starting position. This, together with the assumption we just made, means that at least n^2-3 pixels are part of the ink stain. So the area of the ink stain in cm^2 is greater than or equal to (n^2-3)/n^2. This goes to 1 as n goes to infinity. So the area of the ink stain can't be less than 1.

I don't know if this argument can be made rigorous.

 

[haiha]

I think your argument is quite right. But there are something that I am still not so sure.
The stain can be in any shape and can be separate, so it can involve 2 or more crossing points of the lines. How do you explain that?
Anyway, I will try to prove it by your way, it is nice. Thank you very much.

 

[Fredrik]

That's not a problem. If the ink stain covers more than one point where lines cross that only makes the area of the stain larger. Remember that the most important part of my argument is the claim that the area of the stain is greater than or equal to (n^2-3)/n^2.

I'm more concerned about questions such as this: How do you construct the discrete picture of the ink stain from the continuous picture? Do you e.g consider a pixel to be colored when more than half of its area is covered by the actual ink stain, or only when the whole pixel is covered?

It seems impossible to get this argument to work for fractal patterns.

 

[chronon]

My friends gave me a problem that he said it can be very simple to be proved, but really it is not (to me)

It took me a while to think of it, but once I had it seemed simple.

Set up a grid of 1x1 squares on the paper. Choose one square, and move each of the other squares on top of it. The different bits of ink stain may overlap, but since their area is less than 1, they won't fill the square. Position the net so that a knot is above an empty part of this square. Then none of the knots will coincide with any of the original ink stain.

 

[Fredrik]

Wow, there really is a simple solution! And it works for fractal patterns too. Cool.

 

[haiha]

The solution by chronon is really simple and clear, it does not involve the discrete problem. Excellent.
I also thought of a method which makes it discrete solution. The solution is to prove that when you place the net on to the sheet, the probability of a knot (at least one knot) touches the stain must always smaller than 1. Then there is always a possibility to place the net so that not any knot touches the ink stain. But this solution must turn the stain into discrete pixels first.
Thank you all for your help and interest.