You are not logged in.
It is proven that we can place a maximum of 8 queens, 8 rooks, 14 bishops, 16 kings or 32 knights on an 8x8 chessboard such that no two pieces can attack each other. (let's not talk about pawns here)
For 8 queens, according to Wikipedia, there are 12 fundamental solutions (rotations and reflections count as one solution only) and 92 distinct solutions (rotations and reflections create new solutions). What are the corresponding numbers for placing 32 knights? (You might also want to try rooks (apparently thousands), bishops and kings, but those are probably larger numbers).
Also, if we stick the two opposing edges of the chessboard together to make a cylinder (without bases), how many queens can we place at most on the board? (so that there still is no pair of attacking queens)
Another way to place them is:
Divide the 8x8 chessboard into 16 2x2 subboards. Colour these subboards with alternating colours (black/white etc). Then you can place 32 knights on these new dark/light squares and that's two new solutions.
Because I have almost no idea about programming. That being said, I work in IT, but now I'm working with servers and networks. I forgot all about programming.
@Agishom: I'd like to see a more mathematical solution. In other words, the computer part should be reduced to computing formulae that we deduce purely through maths. Although his solution needed a mathematical start, I need more.
No. When ka surpasses 2012, its remainder drops.
I found a solution anyway. http://math.stackexchange.com/questions/685173/2012-usajmo-problem-5
But I don't quite understand this part:
"So we want to maximize the times where ak≡0(mod2012) or ak≡bk(mod2012)
If k is even, then if a≡0(mod1006) or ak≡bk(mod1006)→a−b≡0(mod1006) we have a desired solution. So, we can make a=b+1006 or a=1006 to satisfy the second congruence for all even numbers. There are 1005 such even k.
Next consider the odd case for k. If k=503 or 3∗503 we just require a≡0(mod4) or a−b≡0(mod4), which we can easily satisfy. For all other k, we must have either ak≡0(mod2012) or a−b≡0(mod2012) which is impossible with the domain. Thus, 2 odd k work.
The minimum is then 1/2(2011−1005−2)=502. One value this is achieved at is f(1006,1010), though it works for all f(1006,4k+2) provided that the domain is considered."
So that isn't a mathematical forum, its a programming/IT forum. Am I correct?
For a given pair of integer a and b (1<=a,b<2012, a =/= b), we define f(a,b) as the number of values for k (1<=k<2012) for which ak leaves a larger remainder than bk when divided by 2012. What is min f(a, b)?
Please provide the detailed solution. Thanks!
I'll meet him up next Tuesday.
Can you please post the detailed solution, or at least the methodology?
Also Agnishom, I think he only proved "if f(n) is odd, n is of the form 2^k - 1". Not the other way around.
Agnishom, I don't understand this part:
"By the inductive hypothesis, this is the number of k such that n - 2^k = 2^j - 1 for some j, i.e. the number of ways to write n = 2^k + 2^j - 1."
Can you please?
For reference, the first 8 values of f(n) I calculated by hand are: 1, 2, 3, 6, 10, 18, 31, 56...
I looked it up on OEIS. The sequence is available on OEIS as "Number of compositions (ordered partitions) of n into powers of 2" - exactly what I need. (They start with 0) A023359
They do have f(15) = 2983 and f(31) = 26805983, furthering my conjecture.
I don't quite grasp the formula section though. Can you please elaborate?
Because I computed the values of f(n) for n = 1 to 10: only 1, 3 and 7 had f(n) odd. Also, I had this same f(n) a month ago, when I saw a problem about calculating f(15) - I think it was odd.
Find the proof. We aren't allow to compute all the values, as we are not allowed to have computers.
By EM? What does that mean? (I haven't been following English math forums for a while)
Is it possible to solve it solely with arithmetic and algebra, and without the use of computers? (so you can't just calculate f(n) for every number and then look at it)
Original wording of question:
>Let f(n) be the number of ways to write n as a sum of powers of 2, where we keep track of the order of summation. For example, f(4) = 6 because 4 can be written as 4, 2+2, 2+1+1, 1+2+1, 1+1+2, and 1+1+1+1. Find the smallest n greater than 2013 for which f(n) is odd.
My conjecture is that f(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k, but I haven't been able to prove it
I've found few similar problems on the Internet. The closest one is at http://mathlesstraveled.com/2008/04/18/challenge-12-sums-of-powers-of-two/ (problem 3). The only difference is that my problem does distiguish 2+1+1 and 1+2+1 for example.
P/S: My older post a year ago about 64 pawns have not been answered yet. Can you please solve that also?
Thanks a lot!
Ok but I can prove that those are not the only cofigurations.
No, that question on the top is the full question.
Well because I won't meet him for another month, and after all he is using this to puzzle me.
He won't give away the answers.
Again, I got it from a secondary school teacher.
That is terribly nonsense, because the black pawns and white pawns are identical except for the colours.
Disregarding the rule that a pawn can't attack another, we still could only have up to 64C32 ways.
a secondary math teacher.
I don't know, but since he isn't posting anything I guess he has no interest.
I think a fair estimate would be 6000 - 6500 ways. Hope the most genius-like people here will do it.
Why isnt Bobbym doing it?
Is nobody really caring about this? I really need it! Please help, people!
It is actually a nightmare to draw them up and count one by one, but I can't find any other way. I say, 99% of the people here can do it, they just have't read it.
So there are those 2 answers, but there are tons of other answers.
For example on a standard chessboard, if a black pawn is present on H4, there are no less than 143 solutions. And there are still other answers, when a white pawn is present on H4.
The question isn't about creating a configure, but counting them all.
Here is a hard problem that 99% of people here will get to answer it in 5 minutes.
"There is an 8x8 chessboard. 32 black pawns and 32 white pawns are to be placed on the board such that no pawn can capture another of the opposite color. Assume that no pawn is promoted, and the rules for the pawns to capture another piece is otherwise in power (i.e. except the promotion rule all other rules concerning the pawn is still used), find the number of ways to place the 64 pawns. (Note that we cannot turn the chessboard)