Math Puzzle: Integer Points(pratikpoddarcse.blogspot.in)
pratikpoddarcse.blogspot.in
Math Puzzle: Integer Points
http://pratikpoddarcse.blogspot.in/2013/04/integer-points.html
19 comments
There are four pairs of values modulo two, so if you have five points some two of them must be the same modulo two. Say these points are A and B. Then A + B = (even, even), and so (A + B) / 2 has integer coordinates.
That was tough to follow, let me restate,
Let the two points be (x1, y1) and (x2, y2) such that x1 % 2 == x2 % 2 and y1 % 2 == y2 % 2, i.e., have the same parity.
Then x1 + x2 = 2 * x3 (is even) and y1 + y2 = 2 * y3 (is even), and (x3, y3) is an integer point.
Given five points, two such points must exist because of the pigeon hole principle.
Let the two points be (x1, y1) and (x2, y2) such that x1 % 2 == x2 % 2 and y1 % 2 == y2 % 2, i.e., have the same parity.
Then x1 + x2 = 2 * x3 (is even) and y1 + y2 = 2 * y3 (is even), and (x3, y3) is an integer point.
Given five points, two such points must exist because of the pigeon hole principle.
So that means that there will be at least on line which the center is an integer point.
There are four possible coordinate parities
Between two points of same parity the difference has the parity (even, even).
As (even, even) is divisible by two there's an integer midpoint.
(even, even), (even, odd), (odd, even), (odd, odd)
Between two points of same parity the difference has the parity (even, even).
As (even, even) is divisible by two there's an integer midpoint.
true, you can always make one of the 4 lines have a slope that is even/even. the point composed of x/2,y/2 will lie on this line.
I don't understand. Choose points (0,0) (0,1) (1,0) (1,2) (2,1) (2,2). What line contains three points?
Diagram:
_OO
O_O
OO_
e: oh, not a point in the original set, any integer point. thanks!
Diagram:
_OO
O_O
OO_
e: oh, not a point in the original set, any integer point. thanks!
I think the question might be better put this way:
Pick 5 random points on an infinite plane. Draw lines between all of them. One of those lines will contain another integer point. Prove this is true for every set of 5 random points.
Pick 5 random points on an infinite plane. Draw lines between all of them. One of those lines will contain another integer point. Prove this is true for every set of 5 random points.
You chose 6 points, and there are 3 line segments among them containing (1,1).
The line segment described by (0,0) (2,2) goes through the integer point (1,1).
[deleted]
[deleted]
This seems rather trivial.
Take two arbitrary points, named A and B, where Ax < Bx (if Ax == Bx, this becomes absurdly simple).
Calculate the delta ∂ between the points, such that ∂x = Bx - Ax and ∂y = By - Ay
Define a third point C such that Cx = Bx + ∂x and Cy = By + ∂y.
C is integral, and is colinear with A and B.
Take two arbitrary points, named A and B, where Ax < Bx (if Ax == Bx, this becomes absurdly simple).
Calculate the delta ∂ between the points, such that ∂x = Bx - Ax and ∂y = By - Ay
Define a third point C such that Cx = Bx + ∂x and Cy = By + ∂y.
C is integral, and is colinear with A and B.
While we're all solving puzzles, can anyone help me with this one?
No doubt you've doodled this shape in your graph paper before: http://i.imgur.com/oY29sBc.png
What function does this slope approximate? It almost a circle, but not quite.
No doubt you've doodled this shape in your graph paper before: http://i.imgur.com/oY29sBc.png
What function does this slope approximate? It almost a circle, but not quite.
This is a quadratic Bézier curve http://en.wikipedia.org/wiki/B%C3%A9zier_curve
Or in other words, it’s a section of a parabola. (As it happens, it’s a parabola tilted 45°, but still.)
It's y=(sqrt(x) - 1)^2
Consider the function l(t) which gives the appropriate line function f(x) for the line going through (t,0). The function we are looking for can then be defined as c(x) := max(l(t)(x), t in (0;1]). Just solve for t and pop it into l(t), et voila.
Consider the function l(t) which gives the appropriate line function f(x) for the line going through (t,0). The function we are looking for can then be defined as c(x) := max(l(t)(x), t in (0;1]). Just solve for t and pop it into l(t), et voila.
Sorry, I accidentally down-voted you when I tried to up-vote you. This answer is absolutely correct. Here is my very similar derivation:
All lines go through (t,0) and (0,1-t). Now take two such lines, one with constant t and another with constant s and find their intersection. We have:
All lines go through (t,0) and (0,1-t). Now take two such lines, one with constant t and another with constant s and find their intersection. We have:
y = 1-t - (1-t)/t * x
y = 1-s - (1-s)/s * x
1-t - (1-t)/t * x = 1-s - (1-s)/s
s-t = (s-t)/(st) * x
x = st
x = t^2
y = (1-t)^2
y = (1 - sqrt(x))^2
sqrt(x) + sqrt(y) = 1sqrt(x)+sqrt(y)=C
LOL. For any two integer points P(i, j), Q(l, m). We have the equation of a line:
y - j = ((m - j) / (l - i)) * (x - i)
Choose x = k * (l - i) + i y = k*(m - j) + j Since i, j, l, m, k are all integers we obtain another integer point. No need 5 points... I may misunderstand the question. :(
y - j = ((m - j) / (l - i)) * (x - i)
Choose x = k * (l - i) + i y = k*(m - j) + j Since i, j, l, m, k are all integers we obtain another integer point. No need 5 points... I may misunderstand the question. :(
I don't see any obvious problem with this counterexample:
(0,5), (3,0), (4,6), (7,1), (9,4)
http://farm9.staticflickr.com/8114/8661127874_f9269f0ee5_b.j...
Is there something I'm missing?
http://farm9.staticflickr.com/8114/8661127874_f9269f0ee5_b.j...
Is there something I'm missing?
(3,0) ... (6,2) ... (9,4)
So comprehensive testing is what you are missing :-)
So comprehensive testing is what you are missing :-)
[deleted](1)
back of the napkin:
take the first 4 points to be a unit box with the lower left point at the origin. You can draw any of 4 lines to the 5th point (x,y). These 4 lines will have slopes x:y, x-1:y, x:y-1, x-1,y-1. You can always arrive at a slope ratio that is evenly divisible through some combination of -1 and reducing the ratio to simplest form. An evenly divisible slope ratio will pass through another point.
example: 5th point (11,4). Choose line with slope 10:4. Divisible by 2, this line passes through the point (5,2). A ratio divisible by 3 would pass through 2 additional points etc.
example: 5th point (11,4). Choose line with slope 10:4. Divisible by 2, this line passes through the point (5,2). A ratio divisible by 3 would pass through 2 additional points etc.
A real proof would work for an arbitrary first four points (with any segment between two not containing a lattice point), but I think nikln already provided this :)
doh, forgot to do the last and most important step, generalizing.
Why would 4 of the points form a square?
If I am remembering correctly, this was on the ARML(American Regions Math League) competition "power question" roughly, say 16-17 years ago. The answers given here from nilkn and the children comments are correct.
[deleted]
[deleted]
choose two integers x and y. These represent the first point on a plain. Only adjacent points can be added i.e. any point can only be 1 integer away from this origin point otherwise there will exist an integer point between the origin point the chosen point. so now we have (x, y), (x+1, y), (x, y+1), and (x+1, y+1). Adding a fifth point anywhere on the graph will make it such that an integer point will exists between two of the selected points.
[deleted](2)
[deleted]
It doesn't hold. Pick (0,1), (0,2), (0,3), (0,4), (0,5) on the plane z = 0
Well, you have five integer points on the same line.
"Suppose we arbitrarily choose 5 integer points in a plane.
Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point."
I am not sure what you mean. I have 'arbitrarily' picked 5 integer points on a plane. Yes, they happen to lie on line. All their line segments contain only these integer points.
Perhaps you mean that is line not on "a plane"? In that case (0,0), (0,1), (0,2), (0,3), (0,1) is another counter example.
Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point."
I am not sure what you mean. I have 'arbitrarily' picked 5 integer points on a plane. Yes, they happen to lie on line. All their line segments contain only these integer points.
Perhaps you mean that is line not on "a plane"? In that case (0,0), (0,1), (0,2), (0,3), (0,1) is another counter example.
In the case of {(0,0),(0,2)}, (0,1) counts as "1 more integer point" - the point has to be not one of the two points generating the line, not a point outside the set of 5 points on the plane.
Okay, we have a solution for the plane. The plane is in
two dimensions. Now, for any positive integer n, generalize the problem to n dimensions.
So, now the problem is, for any positive integer n, given any 2^n + 1 n-tuples of integers, at least two of these n-tuples if added have all even components.
So, now the problem is, for any positive integer n, given any 2^n + 1 n-tuples of integers, at least two of these n-tuples if added have all even components.
[deleted]