Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge Group Title

[UNSOLVED] Combinatorics challenge problem! Suppose you have a chessboard of size \(n\times n\), and you want to place some pawns on it. How many ways are there to place these pawns such that each row and column has an even number of pawns?

  • one year ago
  • one year ago

  • This Question is Open
  1. vf321 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Does chessboard orientation matter?

    • one year ago
  2. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    No.

    • one year ago
  3. vf321 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    OK, well I don't want to make you think that I'm still working on it. I tried for a couple days, but then I gave up.

    • one year ago
  4. andriod09 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    wouldn't you have to fill the entire board so that way every column and every row have the same number of pawns in it?

    • one year ago
  5. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Note necessarily. For example, in a 4x4 chessboard, you can have a 4x2 rectangle filled with pawns.

    • one year ago
  6. andriod09 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah, that's true.

    • one year ago
  7. jasmine2334 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    7

    • one year ago
  8. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm going to try a few n's and see what patterns I notice. n=1, x=0 (1 if the zero-board counts) n=2, x=1 (2 if the zero-board counts) n=3, x=3 (4 if the zero-board counts) assuming that orientation does not matter, therefore rotations and reflections count as the same thing. n=4, x=7 (8 if the zero-board counts) Based on this, x=\[2^{n-1}-1, 2^{n-1} if the zero-board counts.\]

    • one year ago
  9. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @Numb3r1 the zero board is does count, and \(2^{n-1}\) is correct. Can you prove it?

    • one year ago
  10. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I have to prove that adding one more row and one more column doubles the number of possibilities, or find a recursive relation between previous boards. The recursion option seems simpler to me. One moment...

    • one year ago
  11. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    A zero-by-zero board does not exist, so it will obviously have 0 options. The one-by-one board has one option. The two-by-two board has two options (and even-numbered boards will always have a new option in terms of how many pieces are in a row). Adding one row and one column means adding one new option for each option that was available on the previous board (one expanding sideways, one expanding both sideways and upwards). From the 3x3 board, the 4x4 has the same double-expansion factor on the square sub-boards (the 2x2 board and 3x3 with only the corners) but the two rectangular sub-boards can only be lengthened (expanding upwards will lead to the same result as another rectangle or square being lengthened). The 2x2 board in the middle and the 4x4 board are the new options corresponding to the rectangles... This approach isn't leading to an elegant proof, so I'll have to reevaluate.

    • one year ago
  12. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I think your method could lead to a relatively good proof, but it's definitely not what I ended up with. Let me know if you want a hint about my method.

    • one year ago
  13. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\sum_{1}^{n}n!+(n-1)!+....+1!\] seems to work.

    • one year ago
  14. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm not sure I understand what that's supposed to be doing.

    • one year ago
  15. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    @Numb3r1 I apologize, I misread my previous work. \(2^{n-1}\) is not the correct answer. It should be \[\large 2^{(n-1)^2}.\] This is because we consider a rotation of the board to potentially be a different solution.

    • one year ago
  16. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I had already ignored rotations, and that means that I was correct as well! Actually, are you sure it wasn't \[2^{2(n-1)}\]? I don't see how a 7x7 board would have six times as many options if you can rotate it.

    • one year ago
  17. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I am absolutely positive this is the correct solution. Consider the smaller \((n-1)\times(n-1)\) chessboard that is a subboard of the larger one, and start putting pawns on that. What can you say about the placement of pawns on the rest of the board?

    • one year ago
  18. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    My point is that it could be \[(2^{n-1})^{2}=2^{2(n-1)} but 2^{(n-1)^{2}}wont work.\]

    • one year ago
  19. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    To clarify, the first one will, the second will not.

    • one year ago
  20. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    A 7x7 board will have \(2^{36}\) possible solutions, not \(2^{12}\) or \(2^6\). Again, I apologize for leading you down the wrong path for a while :(

    • one year ago
  21. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    For a 3x3 board, \[\left[\begin{matrix} 1& 0& 1 \\ 0&0 &0\\ 1 &0 &1 \end{matrix}\right],\left[\begin{matrix} 1& 1& 0 \\ 1& 1&0\\ 0 &0 & 0\end{matrix}\right]\times4,\left[\begin{matrix} 1&0 & 1\\ 1& 0&1\\ 0&0 &0 \end{matrix}\right]\times4,\left[\begin{matrix} 0& 0&0 \\ 0& 0&0\\ 0 &0 & 0\end{matrix}\right], and what else?\]

    • one year ago
  22. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\begin{bmatrix}0&1&1\\1&1&0\\ 1&0&1\end{bmatrix}\]for example.

    • one year ago
  23. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah, that times four, and then there are two more? I'll have to try another approach to the problem.

    • one year ago
  24. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    the last two I believe are given by \[\begin{bmatrix}1&1&0\\1&0&1\\0&1&1\end{bmatrix}\]and a 90 degree rotation.

    • one year ago
  25. Numb3r1 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    That'll do it.

    • one year ago
  26. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, I've got to sleep now, but I would strongly consider looking at the smaller board of dimensions \((n-1)\times(n-1)\) (which has \((n-1)^2\) boxes), placing some pawns on that, and then looking at where you can place pawns on the one row/column not included in this smaller board.

    • one year ago
  27. mathslover Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Wait for 5 minutes more kg, I am trying.

    • one year ago
  28. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I should correct what I said near the top. Orientation does actually matter. I just had a slight misunderstanding when I read vf321's comment.

    • one year ago
  29. mathslover Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    What should be the correct answer @KingGeorge ?

    • one year ago
  30. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\large 2^{(n-1)^2}\](The \(n-1\) is squared)

    • one year ago
  31. mathslover Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    But if n = 1, then it is 1, but it can not exist ?

    • one year ago
  32. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    If \(n=1\), then \(2^{(n-1)^2}=2^0=1\). The only way would be to have the empty board.

    • one year ago
  33. mathslover Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    lol, empty board also allowed :

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.