Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a combinatorics question:

  1. Imagine you have an $8\times8$ empty chessboard.

  2. You have $10$ identical pawns.

  3. How many different ways can you place those $10$ pawns on the chessboard such that each pawn is at least (Euclidean) distance $X$ away from any of the other pawns?

  4. This is just an example, but what I would like is a function where I can give it the dimensions of the chessboard, the number of pawns that must be on the chessboard, and the minimum distance each pawn must be from any of the other pawns, and then the function returns the number of possible arrangements.

  5. If you don't know how to solve this problem, could you please let me know what subfield of combinatorics that I can learn to solve this problem? For example, is there a clever way of using inclusion-exclusion to solve this problem?

  6. Lastly, if the above problem is too hard, how would you do this if instead of a chessboard that is $8\times 8$, you had a long board that was $64\times 1$?

Thanks!

share|improve this question
    
x distance away meaning rows + columns or straight line distance? –  mathguy Jul 12 '13 at 21:16
    
x distance away means straight line distance. Thanks for clarifying –  628496 Jul 12 '13 at 21:17
4  
Crossposted on MathOverflow. Please note that crossposting between multiple SE sites is highly frowned upon - try one site first, and if you don't get a satisfactory response, ask a moderator to migrate the question to a different site. If you insist on posting in many sites, at least provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to find out that you'd already gotten the solution elsewhere. –  Zev Chonoles Jul 12 '13 at 21:28
    
Do you really think that you can obtain an answer to these questions within $7$ days (as of November 8, 2013)? –  Christian Blatter Nov 8 '13 at 19:23
    
"You have just 10 pawns that are unique because each pawn is at a unique position" doesn't make sense! –  Atul Gangwar Nov 10 '13 at 4:19
show 1 more comment

1 Answer

up vote 1 down vote accepted
+100

For the linear problem (on $p\times1$), this is relatively easy. I give an example : you have 4 pawns that must be at distance 8 (adjacent pawns are at distance 1) on a $30\times 1$ board. So the first pawn can be on cell 1, the second can be on cell 9, the third on cell 17 and the last on cell 25. This is the right most solution, and so the last pawn can only be on cell $p_{4}$ with $25\le p_4 \le 30$.

Once you have fixed $p_4$, then you can verify that $p_1=1+a_1$, $p_2=p_1+8+a_2$, $p_3=p_2+8+a_3$ and $p_4=p_8+8+a_4$, with $a_1+a_2+a_3+a_4=p_4-25$ (and $a_i\ge 0$). How many different $a_i$ verify this ? $\binom{p_4-25+3}{3}$.

So the number you want to find would be : $\sum_{p=25}^{30}\binom{p-25+3}{3}$=$\sum_{p=0}^{5}\binom{p+3}{3}$.

For 10 pawns on a $64\times 1$ lane, with distance $1\le X\le 7$, it would be $$\sum_{p=0}^{63-9X}\binom{p+9}{9}=1+10+55+220+\dots$$.

On a 2 dimensional board, this is (I think) an open question, even for $X=2$. For example the hard square entropy is a problem when we want to know how many ways you can put pawns on a square board with $X=2$ (you can have any number of pawns). No close formula is known to answer this problem. But for small size board, this was computed by computers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.