So I'm reading a beginner level discrete math book which covers topics like set theory and combinatorics. Having a love for math and also chess, one of the things I've found myself wondering is how many possible positions are there with 2 (or less) of the same-color, same-type piece? (I mean, you gotta start somewhere easy and work your way up to the harder stuff, right?)
Here is the general formula: (n^2-n) + 2n + 1
*n represents the number of squares you're working with.
The way I approached solving this problem was fist realizing that I was working with a set of 3 rather than 2, since empty squares need to be accounted for. The member representing empty squares can be selected more than once, while the other members can either be selected once, not at all, or individually. I did the first few n terms by hand to see what the sequence was, and then followed a tutorial for finding the formula for the nth term in a quadratic sequence.
so, for example, the number of permutations involving positions with just two knights or less is 4161.
Your answer is incorrect however. You are counting your permutations twice; since both pieces are the same type and same color, knight A on a1 and knight B on b1 is identical to knight B on a1 and knight A on b1. Only one of these should be counted.
I used a different approach which I can demonstrate covers every possibility. It's actually both mathematically easier and intuitively more comprehendible than the one you've outlined.
I don't want to give you the answer. Try again.
That depends on if you count reflections of a position as different. If so then for two of the same piece it's just 64*63/2
The empty squares are implied by the location of the pieces, so they can be ignored.
This sort of problem becomes quite important when indexing endgame tables, so it has real world applications.
ah yeah, good point, haven't considered that two knights hopping around could land on the same square potentially and that there is no point in differentiating that 😛
Driveby thumbs down from drzwichenzug, and somehow I'm not surprised.
The correct answer is 2081 possible permutations with 2 or fewer pieces of the same type and color on a board of 64 squares. To simplify, first number the squares from 1 to 64. Envision the 1st knight on square 1 and iterate all possibilities for the second knight, from 1 (representing only 1 knight on the board when "both" or on the same square) to 64. 64 possibilities. Then you move the 1st knight to 2 and iterate from 2 to 64 for the 2nd (NOT from 1, since that would be counting a position already counted)... 63 possibilities. This continues until you get to "both" knights on square 64, so you get the sum of the series of integers from 1 to 64 as the answer (sum of an even series of integers from 1 to n is (n+1)*n/2). You then must consider the last case since you are saying 2 OR FEWER knights; the empty board; so one more.
65*64/2 +1 is the final answer; 2081.
I'm sure DrZ will find a reason to thumb this down too. For some reason it's personal with that guy.
Without reflection...
(Pieces, Positions)
(0, 1), (1, 64), (2, (64*63)/2), so 1+64+2016 = 2081
Same result as #6.
I would add that one just need to take time to make a more precise question. The wrong answer to one question, may be the right answer to another. If the initial question was not precise enough. then multiple answers declining (ventilating) the more precise questions version and giving the answers would be correct answers for each. sometimes the fun is detecting the question to which an answer is the right one. So you all got it right (what matter is the relation between question and answer). sorry if that looks like rambling, it is just that I really like the art of asking questions....
@dboing Well, that is why I specifically explained the problem with the OP's answer; he was including juxtapositions. The question phrased it as 2 or fewer pieces of the SAME TYPE AND COLOR. In that case, swapping the locations of the knights is identical.
OP's answer would have been correct, had he asked about two pieces of the same type and OPPOSITE color or fewer. In that case, juxtaposition does indeed matter.
It gets even more fun if we say something like, "two or fewer knights of EITHER color, not counting reflections and rotations." Now we have a math problem where one must be much more careful in the conception of a solution!
So yes, the phrasing of the question must be precise, but the inclusion of the phrase I emphasized is sufficient to formulate the correct answer, and to eliminate the answer where the pieces are identifiably distinct.
@phoenixshade I still think it is more fun to consider all the questions, like you did. What is to be learned is the fact that same type and color is not enough. It does not mean that they are indistinguishable, or that they are not. just that they would potentially occupy certain squares. In fact the "correct answer" is to ask that question.... But i am just pointing to the flow of the discussion, not its content. This imprecision in question is quite often the case, and depends on assumptions of the OP.
I think it is a good exercise to ask for which it is, when answering. And more generally (here lucky that we could enumerate the questions), it may happen that a question does not have an easy answer, and that the work to answer another question might be easier, but that the work in creative thinking is at reformulating a better defined problem. Make the art of the question the focus, is just what I meant (often missing from "platonic" way of teaching math. proofs).
