Author |
Topic: Parallelogram for sure with enough checkers (Read 803 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Parallelogram for sure with enough checkers
« on: Mar 1st, 2006, 7:14pm » |
 Quote  Modify
|
Show that if 16 checkers are on an 8 by 8 checkerboard, at most one per square, then some four of the checkers occupy four squares whose centers are the vertices of a parallelogram with positive area.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Parallelogram for sure with enough checkers
« Reply #1 on: Mar 2nd, 2006, 7:38pm » |
Quote Modify
|
Number the rows and columns with (0-7) to identify each location with a coordinate pair (x, y). For any two checkers at locations (a, b) and (c, d), define their "displacement vector" = (c - a, d - b) if c >= a, and to be (a - c, b - d) otherwise. The x-value of displacement vectors can be anything from 0 to +7, but the y-value can range from -7 to +7. However, the vector (0,0) will not occur. Hence there are 119 possible displacement vectors.
Two pairs of checkers form opposite sides of a parallelogram if and only if the displacement vectors of the pairs are the same. For 16 checkers, there are C(16,2) = 120 pairs. Since there are only 119 possible values for displacement vectors, at least two pairs must have the same vector.
Note also that 15 checkers is not enough, as filling the left column and bottom row does not create any parallelograms.
|
| « Last Edit: Mar 2nd, 2006, 7:40pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #2 on: Mar 2nd, 2006, 8:51pm » |
Quote Modify
|
Very nice! Very different from my proof, and equally short. Your proof explains better why 16 checkers is the minimum. My proof shows the existence of both a parallelogram with one pair of opposite sides vertical and one with one pair of opposite sides horizontal (which two could be the same parallelogram), suggesting that one might be able to get away with fewer checkers than 16.
Both proofs show some "Calendar Magic". Given any 16 elements from {1,...,64}, there exist four of the given numbers with the property that the sum of two of these four equals the sum of the other two of the four.
Of course, for this problem maybe one can get away with fewer than 16 elements, since the "parallelogram" need not have positive area for this problem.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Parallelogram for sure with enough checkers
« Reply #3 on: Mar 3rd, 2006, 12:45am » |
Quote Modify
|
I had the same idea as Icarus's, but then somehow realized that it won't work: the argument presented does not rule out the parallelograms with 0-area.
Consider the Icarus example with 15 checkers: although there is no parallelogram satisfying the conditions of the problem, there are many pairs with the same displacement vector, e.g. (0,1), (0,2) and (0,4), (0,5).
|
| « Last Edit: Mar 3rd, 2006, 12:45am by Barukh » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #4 on: Mar 3rd, 2006, 6:01am » |
Quote Modify
|
You are so right, barukh! But Icarus's solution works beautifully for the "Calendar Magic" problem, while my proof fails utterly on it.
Does Icarus's solution generalize to calendars with m rows and n columns, i.e., the set {1,...,m*n}?
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #5 on: Mar 3rd, 2006, 8:13am » |
Quote Modify
|
Drat! I am wrong again! Icarus's solution does not work for the "Calendar Magic" problem. Checkers at (0,0), (0,1), and (0,2) determine two checker pairs producing the same displacement vector. However, this is only 3 checkers, not 4.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #6 on: Jul 4th, 2006, 3:06pm » |
Quote Modify
|
Since there is as yet no correct solution to this problem, I presume that my erroneous comments are the cause. Is it time for a hint? If you can seperate the wheat from my chaff, you already have a hint.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #7 on: Jul 13th, 2006, 11:04am » |
Quote Modify
|
| hidden: | I prove the more general result:
If m+n checkers are placed on an m by n checkerboard, at most one checker per square, then some four of the checkers occupy four squares whose centers are the vertices of a parallelogram with positive area.
Proof. If there are x>0 checkers in a column (containing m squares), then there are at least x-1 distinct "differences", i.e., the number of pawn moves for one checker to move in that column to the other checker; because each checker below the "top" checker most move a different number of squares to reach that top checker.
For each column i, from 1 to n, let ai be the number of selected checkers in that column. Choose ai-1 pairs of checkers in that column with distinct differences, for each i. Then
a1-1 + ... + an-1=m+n-n=m.
Since a column has exactly m checkers, there can be at most m-1 distinct differences for two checkers in one column. Hence some difference is repeated in the above sum. Since, in addition, we have chosen no checker pairs with repeated differences within a column, some two distinct columns have checker pairs with the same difference. Therefore, the centers of the squares these four checkers occupy form the vertices of a parallelogram with positive area. |
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Parallelogram for sure with enough checkers
« Reply #8 on: Jul 25th, 2006, 2:15pm » |
Quote Modify
|
Nice!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Parallelogram for sure with enough checkers
« Reply #9 on: Jul 29th, 2006, 5:55am » |
Quote Modify
|
I second Icarus. Nice demonstration! 
In fact, ecoist, you have shown a bit more: that under the stated conditions, there exists a parallelogram with at least one side parallel to the side of the board.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #10 on: Jul 29th, 2006, 10:07am » |
Quote Modify
|
Thanks, Icarus and Barukh. Regarding sides parallel to the sides of the board, I have another problem I hesitate to post, fearing it may be a special case of a theorem (about 0,1-matrices?).
Given 58 checkers on a 14x14 checkerboard, at most one checker per square, there exist four of the given checkers which lie on squares whose centers form the vertices of a nondegenerate rectangle with all sides parallel to a side of the checkerboard.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Parallelogram for sure with enough checkers
« Reply #11 on: Aug 1st, 2006, 5:23pm » |
Quote Modify
|
| hidden: |
There are C(14,2) possible pairs of rows; if column i has ni checkers on it, there are C(ni,2) pairs of rows both containing checkers on column i. No two columns can share the same row pairs, so the ni satisfy
Sum ni = 58
Sum C(ni,2) <= C(14,2) = 91
If nj >= nk + 2, we can decrease the second sum while keeping the first constant by increasing nk by 1 and decreasing nj by 1. So we need only check whether there are ni satisfying the conditions where the values are at most one apart. This requires 12 values of 4 and 2 values of 5; but then the second sum is 92.
Generalizing to arbtrary side length n, we get an upper bound asymptotic to n3/2.
|
|
| « Last Edit: Aug 1st, 2006, 5:26pm by Deedlit » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Parallelogram for sure with enough checkers
« Reply #12 on: Aug 1st, 2006, 6:40pm » |
Quote Modify
|
Right on, Deedlit! Corollary to what you did:
Let G be an undirected graph with no loops or multiple edges, with 14 nodes and at least 29 edges. Then G has a 4-cycle.
|
| « Last Edit: Aug 4th, 2006, 10:40am by ecoist » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print