Trgt_2021_explosion's blog

By Trgt_2021_explosion, history, 7 months ago,

Hi Almighty CF Community,

First I googled a lot but didn't get any explanation.(However code is available)

I feel it difficult to solve problems of type "no of ways to arrange some elements of chess so that they are attacking/not attacking each other." I was solving CSES Two Knights problem and I am struggling to come up by a general formula.

I will request if any one can explain the idea behind such problems in general? or at least for this Two Knights problem.

$If \,you\, know \,some \,chess \,based \,problems, \,I \,will\, request\, you \,to \,please \,share \,it. \,Thanks.$

• +3

 » 7 months ago, # |   0 If two knight attack each other then they will be in 2*3 rectangle or 3*2 rectangle. So the number of ways of placing them is (n-1)*(n-2)+(n-2)*(n-1). Also in each rectangle no ways of placing the knight is 2. So total ways of placing knight so that they attack each other will be 2*2*(n-1)*(n-2). So the number of ways such that knight do not attack each other will be n*n*(n*n-1)/2 — 4*(n-1)*(n-2)
•  » » 7 months ago, # ^ |   0 Thanks for the reply. One doubt total no of arrangement is $n^2(n^2-1)$ right? Because all the cells of chess are unique and this two knights are also different.
•  » » » 7 months ago, # ^ |   0 Two knights are same as it is not mentioned different explicitly in the question. So interchanging the knights position will not going to create new ways.
•  » » 2 weeks ago, # ^ |   0 How did u think like this! :O U just made my day!! its soo beautiful!!
 » 7 months ago, # |   0 Auto comment: topic has been updated by Trgt_2021_explosion (previous revision, new revision, compare).
 » 7 months ago, # | ← Rev. 2 →   0 My General Interpretation(after reading the comment by dolamanee6122)Lets say $e1$ and $e2$ are two elements of chess. And we need to find "No of ways so that the attack each other/Not attack each other"$Total\, no\, of\, ways$ to place these two are $n^2(n^2-1)/2 \,\,or\,\, n^2(n^2-1)$ if $e1$ and $e2$ are identical and non-identical respectively.Now find $Minimum\,Region\,of\,attack$ and $Maximum \,Region \,of \,attack$ for $e1$ and $e2$.$Minimum\,Region\,of\,attack$ — a rectangle of size $m_1*m_2$ in which they can attack each otherSimilarly $Maximum\,Region\,of\,attack$ — a rectangle of size $M_1*M_2$Now we can find no of rectangles of a given size in a grid easily. So our final result will be $Total\, no\, of\, ways\, - \displaystyle \sum\limits_{i = m_1}^{M_1}\sum\limits_{j = m_2}^{M_2} (No\,of \,ways\, to \,choose\, rectangles \,of \,size\, (i*j )in\, given\, grid)*K_{ij}$ (where $K_{ij}$ is no of arrangement of $e1$ and $e2$ in the rectangle of size $(i*j)$ s.t. they are attacking each-other.) Finding rectangle of size $i*j$ in a grid of size $m*n$ is straight. It's $(m-i+1)*(n-j+1)$ (for $i\leq m, j\leq n$)Please point out if I am wrong.
•  » » 2 months ago, # ^ |   0 How is it that the total number of arrangments possible is n^2(n^2-1)/2. What is the mathematics involved in this?
 » 6 months ago, # |   0 A better explaination for this problem is provided here:- https://math.stackexchange.com/questions/3266257/number-of-ways-two-knights-can-be-placed-such-that-they-dont-attack/3266324#3266324
 » 2 months ago, # |   0 There is no need to think. For each number of possible moves (2, 3, 4, 6 and 8) it is very easy to count the number of squares where you have this number of possible moves. For example, 2 moves are possible only from the corners, and there are 4 corners.
 » 2 weeks ago, # |   -8 you can use Lagrange polynomial to find the expression, just take enough points( n, answer pairs) and brute force it.
•  » » 2 weeks ago, # ^ |   +18 Can you explain why it is a polynomial?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   -12 actually, sometime back I was solving a problem in which I used this and got the correct result. I don't have solid proof, but these were my thoughts that kinda convinced me and might convince you though I agree it's somewhat wage, let's increase the size of the chessboard by 1 unit, f(n+1)-f(n) is a polynomial in n because only polynomial more new places/orientation are created. (to be specific O($n^2$))(you can argue it might be a difference of some Taylor series expansion of some non-polynomial, but then again that function must be a mapping to infinite integer set, so that makes it difficult to not be polynomial according to my understanding, I am open to any suggestion on this.)
•  » » » » 2 weeks ago, # ^ |   0 $f(n + 1) - f(n)$ is $O(n^2)$, but that doesn't make it a polynomial, it only means that it's bounded above by a polynomial. I don't know what the text in the brackets means.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 4 →   +12 do you agree f(n+1)-f(n) will be polynomial? Rest of this only make sense to me if you agree to it, I don't know, seeing the downvotes I think everybody knows/says it's not polynomial,then it's fine, I should be wrong, just igonre it, or give it downvotes.In bracket, I meant that as some nonpolynomial can be written as polynomial as their Taylor series expansion, but I couldn't think of such a valid function, that have f(n+1)-f(n) O($n^2$) and an integer as output for every integer input.
•  » » » » » » 2 weeks ago, # ^ |   0 It will, but only if we don't look at $n \le 5$ and not for the reasons you mentioned. I just did the math like dalex told.There are many functions that have $f(n+1)-f(n) \in O(n^2)$ that are not polynomial. For example the minimum of two cubics. And a lot of functions that are the answer to some combinatorics problem.
•  » » » » » » » 2 weeks ago, # ^ |   -10 Interesting, I never encountered a non-polynomial combinatorial expression that isn't exponential and is Integer-valued.can you give some examples?
 » 2 weeks ago, # | ← Rev. 2 →   0 You can watch this video : Editorial to 3 knights variation of the same problem. The audio is not that clear though, Still, you can understand the concept from this. Also, these sequences are generally available in OEIS, and hence googling the first few values works most of the time.