Mixing
Integer midpoint
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Two points $(c, d, e),(x, y, z) in mathbbR^3$, we say that the midpoint of these two points is the point with coordinates
$left(fracc+x2
,
fracd+y2
,
frace+z2right)$
Take any set $S$ of nine points from $mathbbR^3$
with integer coordinates.
Prove that there must be at least one pair of points
in $S$ whose midpoint also has integer coordinates.
I've tried to do an example with set
$$S=(2,2,2),(1,8,2),(3,4,5),(5,2,2),(4,2,9),\(2,1,4),(6,8,2),(0,0,0),(5,2,3)$$
So taking $2$ points, $(3,4,5)$ and $(5,2,3)$
so $(3+5)/2=4$, $(4+2)/2=3$, $(5+3)/2 = 4$, which are integers. I'm wanting this argument to hold in general and I'm finding it tricky to prove this does anyone have suggestions would be grateful!
combinatorics discrete-mathematics
edited 45 mins ago
Eleven-Eleven
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
favorite
Two points $(c, d, e),(x, y, z) in mathbbR^3$, we say that the midpoint of these two points is the point with coordinates
$left(fracc+x2
,
fracd+y2
,
frace+z2right)$
Take any set $S$ of nine points from $mathbbR^3$
with integer coordinates.
Prove that there must be at least one pair of points
in $S$ whose midpoint also has integer coordinates.
I've tried to do an example with set
$$S=(2,2,2),(1,8,2),(3,4,5),(5,2,2),(4,2,9),\(2,1,4),(6,8,2),(0,0,0),(5,2,3)$$
So taking $2$ points, $(3,4,5)$ and $(5,2,3)$
so $(3+5)/2=4$, $(4+2)/2=3$, $(5+3)/2 = 4$, which are integers. I'm wanting this argument to hold in general and I'm finding it tricky to prove this does anyone have suggestions would be grateful!
combinatorics discrete-mathematics
edited 45 mins ago
Eleven-Eleven
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
5
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
1
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
2
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Two points $(c, d, e),(x, y, z) in mathbbR^3$, we say that the midpoint of these two points is the point with coordinates
$left(fracc+x2
,
fracd+y2
,
frace+z2right)$
Take any set $S$ of nine points from $mathbbR^3$
with integer coordinates.
Prove that there must be at least one pair of points
in $S$ whose midpoint also has integer coordinates.
I've tried to do an example with set
$$S=(2,2,2),(1,8,2),(3,4,5),(5,2,2),(4,2,9),\(2,1,4),(6,8,2),(0,0,0),(5,2,3)$$
So taking $2$ points, $(3,4,5)$ and $(5,2,3)$
so $(3+5)/2=4$, $(4+2)/2=3$, $(5+3)/2 = 4$, which are integers. I'm wanting this argument to hold in general and I'm finding it tricky to prove this does anyone have suggestions would be grateful!
combinatorics discrete-mathematics
edited 45 mins ago
Eleven-Eleven
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Two points $(c, d, e),(x, y, z) in mathbbR^3$, we say that the midpoint of these two points is the point with coordinates
$left(fracc+x2
,
fracd+y2
,
frace+z2right)$
Take any set $S$ of nine points from $mathbbR^3$
with integer coordinates.
Prove that there must be at least one pair of points
in $S$ whose midpoint also has integer coordinates.
I've tried to do an example with set
$$S=(2,2,2),(1,8,2),(3,4,5),(5,2,2),(4,2,9),\(2,1,4),(6,8,2),(0,0,0),(5,2,3)$$
So taking $2$ points, $(3,4,5)$ and $(5,2,3)$
so $(3+5)/2=4$, $(4+2)/2=3$, $(5+3)/2 = 4$, which are integers. I'm wanting this argument to hold in general and I'm finding it tricky to prove this does anyone have suggestions would be grateful!
combinatorics discrete-mathematics
combinatorics discrete-mathematics
edited 45 mins ago
Eleven-Eleven
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 45 mins ago
Eleven-Eleven
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 45 mins ago
Eleven-Eleven
8,67362554
edited 45 mins ago
Eleven-Eleven
8,67362554
edited 45 mins ago
Eleven-Eleven
8,67362554
8,67362554
asked 2 hours ago
sphynx888
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 hours ago
sphynx888
354
asked 2 hours ago
sphynx888
354
354
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
sphynx888 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
5
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
1
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
2
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago
add a comment |Â
5
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
1
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
2
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago
5
5
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
1
1
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
2
2
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Just to reiterate what I said earlier, if we list the possible parities of the $3$-tuples, we have
$$(e,e,e),(e,e,o),(e,o,e),(e,o,o),(o,e,e),(o,e,o),(o,o,e),(o,o,o)$$
So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;
$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$
So in order for your midpoint to be an integer, we need to add either two evens or two odds, not even and odd. Therefore, since we have 9 points, assuming our first 8 points are all of different parity as above, the 9th must be one of these 8 possibilities. If you add up the two number that have the same parity structure, this will yield an even number, which is divisible by 2, and so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.
answered 7 mins ago
Eleven-Eleven
8,67362554
add a comment |Â
up vote
5
down vote
Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and show the following more general statement: in any set of $2^n+1$ points in $mathbbZ^n$ there is at least one pair that has the midpoint in $mathbbZ^n$.
answered 1 hour ago
Robert Z
86.4k1056125
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Just to reiterate what I said earlier, if we list the possible parities of the $3$-tuples, we have
$$(e,e,e),(e,e,o),(e,o,e),(e,o,o),(o,e,e),(o,e,o),(o,o,e),(o,o,o)$$
So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;
$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$
So in order for your midpoint to be an integer, we need to add either two evens or two odds, not even and odd. Therefore, since we have 9 points, assuming our first 8 points are all of different parity as above, the 9th must be one of these 8 possibilities. If you add up the two number that have the same parity structure, this will yield an even number, which is divisible by 2, and so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.
answered 7 mins ago
Eleven-Eleven
8,67362554
add a comment |Â
up vote
1
down vote
accepted
Just to reiterate what I said earlier, if we list the possible parities of the $3$-tuples, we have
$$(e,e,e),(e,e,o),(e,o,e),(e,o,o),(o,e,e),(o,e,o),(o,o,e),(o,o,o)$$
So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;
$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$
So in order for your midpoint to be an integer, we need to add either two evens or two odds, not even and odd. Therefore, since we have 9 points, assuming our first 8 points are all of different parity as above, the 9th must be one of these 8 possibilities. If you add up the two number that have the same parity structure, this will yield an even number, which is divisible by 2, and so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.
answered 7 mins ago
Eleven-Eleven
8,67362554
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Just to reiterate what I said earlier, if we list the possible parities of the $3$-tuples, we have
$$(e,e,e),(e,e,o),(e,o,e),(e,o,o),(o,e,e),(o,e,o),(o,o,e),(o,o,o)$$
So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;
$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$
So in order for your midpoint to be an integer, we need to add either two evens or two odds, not even and odd. Therefore, since we have 9 points, assuming our first 8 points are all of different parity as above, the 9th must be one of these 8 possibilities. If you add up the two number that have the same parity structure, this will yield an even number, which is divisible by 2, and so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.
answered 7 mins ago
Eleven-Eleven
8,67362554
Just to reiterate what I said earlier, if we list the possible parities of the $3$-tuples, we have
$$(e,e,e),(e,e,o),(e,o,e),(e,o,o),(o,e,e),(o,e,o),(o,o,e),(o,o,o)$$
So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;
$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$
So in order for your midpoint to be an integer, we need to add either two evens or two odds, not even and odd. Therefore, since we have 9 points, assuming our first 8 points are all of different parity as above, the 9th must be one of these 8 possibilities. If you add up the two number that have the same parity structure, this will yield an even number, which is divisible by 2, and so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.
answered 7 mins ago
Eleven-Eleven
8,67362554
answered 7 mins ago
Eleven-Eleven
8,67362554
answered 7 mins ago
Eleven-Eleven
8,67362554
answered 7 mins ago
Eleven-Eleven
8,67362554
8,67362554
add a comment |Â
add a comment |Â
up vote
5
down vote
Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and show the following more general statement: in any set of $2^n+1$ points in $mathbbZ^n$ there is at least one pair that has the midpoint in $mathbbZ^n$.
answered 1 hour ago
Robert Z
86.4k1056125
add a comment |Â
up vote
5
down vote
Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and show the following more general statement: in any set of $2^n+1$ points in $mathbbZ^n$ there is at least one pair that has the midpoint in $mathbbZ^n$.
answered 1 hour ago
Robert Z
86.4k1056125
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and show the following more general statement: in any set of $2^n+1$ points in $mathbbZ^n$ there is at least one pair that has the midpoint in $mathbbZ^n$.
answered 1 hour ago
Robert Z
86.4k1056125
Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and show the following more general statement: in any set of $2^n+1$ points in $mathbbZ^n$ there is at least one pair that has the midpoint in $mathbbZ^n$.
answered 1 hour ago
Robert Z
86.4k1056125
answered 1 hour ago
Robert Z
86.4k1056125
answered 1 hour ago
Robert Z
86.4k1056125
answered 1 hour ago
Robert Z
86.4k1056125
86.4k1056125
add a comment |Â
add a comment |Â
sphynx888 is a new contributor. Be nice, and check out our Code of Conduct.
sphynx888 is a new contributor. Be nice, and check out our Code of Conduct.
sphynx888 is a new contributor. Be nice, and check out our Code of Conduct.
sphynx888 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2946992%2finteger-midpoint%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
5
These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"...
– Eleven-Eleven
2 hours ago
1
pigeon hole principle is probably onto the right track ?
– sphynx888
1 hour ago
2
By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight.
– John Hughes
1 hour ago