Posts in Mathematics (4 found)
Susam Pal 1 months ago

Triangle-Free Cayley Graph

In this note I elaborate the proof of a claim regarding Cayley graphs of symmetric groups with transpositions as generators that I found in the book Algebraic Graph Theory by Chris Godsil and Gordon Royle. This claim appears as commentary in Section 3.10 about Transpositions . Here I present it in the form of a theorem along with a complete proof. Theorem. If \( \mathcal{T} \) is a set of transpositions, then the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}) \) has no triangles. Proof. Suppose the vertices \( a, b, c \in \operatorname{Sym}(n) \) form a triangle in the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}). \) Since multiplication by \( a^{-1} \) is an automorphism of the Cayley graph (by the proof of Theorem 3.1.2 that comes earlier), the vertices \( e, ba^{-1}, ca^{-1} \) form a triangle too. Let us label them as \( e, b', c' \) respectively. Now by the definition of a Cayley graph, for any two vertices \( a, b \in \operatorname{Sym}(n), \) we have \begin{align*} a \sim b & \iff ba^{-1} \in \mathcal{T} \\ & \iff ba^{-1} = g \\ & \iff b = ga \end{align*} for some \( g \in \mathcal{T}. \) Therefore \begin{align*} e \sim b' & \iff b' = ge = g, \\ e \sim c' & \iff c' = he = h, \\ b' \sim c' & \iff c' = lb' \end{align*} for some \( g, h, l \in \mathcal{T}. \) Note that the last equality gives \[ l =c'b'^{-1} = hg^{-1} = hg \in \mathcal{T} \] Therefore \( g, h, hg \in \mathcal{T}. \) However, this is impossible since the product of two transpositions is \( e, \) a \( 3 \)-cycle or a product of two disjoint transpositions. For example, \( (12)(12) = e, \) \( (12)(13) = (123) \) and \( (12)(24) = (12)(24). \) Therefore \( hg \) cannot be a transposition, i.e. \( hg \notin \mathcal{T}. \) This is a contradiction. Therefore the vertices \( a, b, c \) cannot form a triangle. We conclude that the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}) \) has no triangles. Read on website | #mathematics

Mathematics
0 views
Susam Pal 4 months ago

Prime Number Grid Explorer

A simple single-page HTML application to explore the distribution of prime numbers in a grid. Choose a starting number along with the number of rows and columns and the page generates the corresponding grid. Read on website | #web | #mathematics | #technology

web-development Web Development html HTML Mathematics
0 views
Susam Pal 5 months ago

Mutually Attacking Knights

How many different ways can we place two identical knights on an \( n \times n \) chessboard so that they attack each other? Can we find a closed-form expression that gives this number? This is the problem we explore in this article. A knight moves two squares in one direction, then one square perpendicular to it, forming an L-shaped path. If a piece occupies the destination square, the knight captures it. If two knights are placed such that each can capture the other in a single move, then we say the knights attack each other. We want to determine the number of ways to place two identical knights on an \( n \times n \) chessboard so that they attack each other. The above illustration shows just one of several ways two knights can attack each other on a \( 3 \times 3 \) board. There are, in fact, a total of eight such placements, shown below. Let \( f(n) \) denote the number of ways we can place two identical knights on an \( n \times n \) chessboard such that they attack each other, where \( n \ge 1. \) A \( 1 \times 1 \) board has room for only one knight, so we define \( f(1) = 0. \) On a \( 2 \times 2 \) board, a knight cannot move two squares in any direction and therefore cannot attack. Therefore, \( f(2) = 0. \) To summarise, \[ f(1) = f(2) = 0. \] From the illustration above, we see that \( f(3) = 8. \) We want to find a closed-form expression for \( f(n). \) We will analyse this problem from various perspectives. We begin with a couple of needlessly complicated approaches, followed by a simple and elegant solution. While I personally enjoy these long-winded explorations, if you prefer a more direct solution, please skip ahead to Counting Placements From Minimal Attack Sections . Before we proceed, let us introduce the term mutually attacking knight placement to mean a placement of two knights on the chessboard such that they attack each other. Unless stated otherwise, the two knights are identical. This term will serve as a convenient shorthand for referring to such placements. We now turn to the needlessly complicated solution promised in the previous section. We analyse the new mutually attacking knight placements introduced when an existing board is enlarged by adding a row and a column. Let us define \[ \Delta f(n) = f(n) - f(n - 1) \] for \( n \ge 2, \) so that \( \Delta f(n) \) denotes the new mutually attacking knight placements introduced when an \( (n - 1) \times (n - 1) \) board is expanded to size \( n \times n \) by adding one row and one column. For brevity, we will avoid restating the process of enlarging an \( (n - 1) \times (n - 1) \) board to an \( n \times n \) board by adding one row and one column whenever we refer to new placements. Instead, we use the term new placements on an \( n \times n \) board to refer to \( \Delta f(n). \) It is to be understood that these new placements are the mutually attacking knight placements introduced by enlarging the board from size \( (n - 1) \times (n - 1) \) to \( n \times n. \) Without loss of generality, suppose the new row and column are added to the bottom and right respectively. We already know that \begin{align*} \Delta f(2) & = f(2) - f(1) = 0 - 0 = 0, \\ \Delta f(3) & = f(3) - f(2) = 8 - 0 = 8. \\ \end{align*} We will now find \( \Delta f(n) \) for \( n \ge 4. \) To do this, we first categorise the newly added squares due to board expansion, into four types, as illustrated below. Here is a brief description of each square type: We now calculate how many new mutually attacking knight placements are introduced by these additional squares as the board expands. We proceed with a case-by-case analysis for each square type. There are three squares of type A. If we place one knight on a type A square, there are two positions for the second knight such that the two knights attack each other. Since there are three such squares, we get a total of \( 3 \times 2 = 6 \) new mutually attacking knight placements. There are two squares of type B. If we place one knight on a type B square, there are three positions for the second knight such that the two knights attack each other. Since there are two such squares, we get a total of \( 2 \times 3 = 6 \) new mutually attacking knight placements. The number of type C squares depends on the board size. When we increase the size of a board from \( (n - 1) \times (n - 1) \) to \(n \times n, \) where \( n \ge 4, \) we add \( n^2 - (n - 1)^2 = 2n - 1 \) new squares. Among these, \( 3 \) are of type A, \( 2 \) are of type B and \( 2 \) are of type D. That gives us a total of \( 7 \) squares of type A, B or D. The remaining \( 2n - 1 - 7 = 2n - 8 \) squares are therefore of type C. Note that when the board size increases from \( 3 \times 3 \) to \( 4 \times 4, \) there are \( 2 \times 4 - 8 = 0 \) squares of type C. However, for a board of size \( 5 \times 5 \) or greater, there is a positive number of type C squares since \( 2n - 8 \gt 0 \) if and only if \( n \gt 4. \) If we place one knight on a type C square, there are four positions for the second knight such that the two knights attack each other. Since there are \( 2n - 8 \) such squares, we get a total of \( 4(2n - 8) = 8(n - 4) \) new mutually attacking knight placements. There are two squares of type D. As with type B squares, placing one knight on a type D square yields three positions for the second knight such that the two knights attack each other. This gives \( 2 \times 3 = 6 \) potentially new placements. However, unlike type B squares, not all of these placements are new . The two placements where one knight is on the right edge and the other on the bottom edge were already counted in a previous subsection. For example, when we increase the board size from \( 3 \times 3 \) to \( 4 \times 4, \) both the placements described in the previous paragraph appear while analysing the placements with a knight on a type B square. More generally, for any board of size \( n \times n \) with \( n \ge 5, \) these placements occur while analysing the placements with a knight on a type C square. Therefore the total number of new mutually attacking knight placements is \( 2 \times 3 - 2 = 4. \) Another way to describe this result is to observe that when one knight is placed on a type D square, only two positions for the second knight yield new mutually attacking knight placements. Since there are two type \( D \) squares, we get a total of \( 2 \times 2 = 4 \) new mutually attacking knight placements. If we add the number of new mutually attacking knight placements found in each of the cases above, we get \[ \Delta f(n) = 6 + 6 + 8(n - 4) + 4 = 8(n - 2) \] new mutually attacking knight placements as the board size increases from \( (n - 1) \times (n - 1) \) to \( n \times n, \) where \( n \ge 4. \) We already know that \( \Delta f(2) = 0 \) and \( \Delta f(3) = 8. \) Surprisingly, the above formula produces the correct values for those cases as well. Therefore, we can generalise this result as \[ \Delta f(n) = 8(n - 2) \] for all \( n \ge 2. \) We can now calculate \( f(n) \) for \( n \ge 1 \) as follows: \begin{align*} f(n) & = \sum_{k = 1}^n f(k) - \sum_{k = 1}^{n - 1} f(k) \\ & = \sum_{k = 1}^n f(k) - \sum_{k = 2}^n f(k - 1) \\ & = f(1) + \sum_{k = 2}^n (f(k) - f(k - 1)) \\ & = f(1) + \sum_{k = 2}^n \Delta f(k) \\ & = 0 + \sum_{k = 2}^n 8(k - 2) \\ & = 8 \sum_{k = 0}^{n - 2} k \\ & = \frac{8(n - 2)(n - 1)}{2} \\ & = 4(n - 1)(n - 2). \end{align*} To summarise, we now have a closed form expression for \( f(n). \) For all \( n \ge 1, \) we have \[ f(n) = 4(n - 1)(n - 2). \] The previous section took a long-winded path to arrive at a closed form expression for \( f(n). \) In this section, we will reach the same result that is still a bit drawn out, but not quite as much as before. This time, instead of looking only at the new squares created when the board grows, we consider every square on the board. To make the counting easier, we no longer treat the knights as identical. We first work with two distinct knights, count the mutually attacking knight placements and then divide the total by \( 2 \) to get the result for identical knights. Here, we introduce the term attacking degree of a square to mean the number of squares a knight can move to from that square in a single move. In other words, the attacking degree of a square is the number of squares that would be attacked if a knight were placed on it. For example, the corner squares have an attacking degree of \( 2. \) Let us now label each square with its attacking degree. A \( 1 \times 1 \) board has only one square of attacking degree \( 0 \) since a knight placed on it has nothing to attack. Similarly, each square of a \( 2 \times 2 \) board has attacking degree \( 0 \) too. On a \( 3 \times 3 \) board, all squares have attacking degree \( 2 \) except the centre square, whose attacking degree is \( 0. \) In other words, placing a knight on any square other than the middle one gives exactly two possible positions for the other knight so that they attack each other. With eight such squares, we get \( 8 \times 2 = 16 \) mutually attacking knight placements when the two knights are distinct. If we divide this number by \( 2, \) we get \( 8 \) which is indeed the number of mutually attacking knight placements on a \( 3 \times 3 \) board when the two knights are identical. This matches the earlier result \( f(3) = 8. \) Let \( g(n) \) be the number of mutually attacking knight placements on an \( n \times n \) board when the knights are distinct. Then \( g(n) \) is simply the sum of the attacking degrees of all squares on the board. As before, let \( f(n) \) denote the number of mutually attacking knight placements on an \( n \times n \) board when the two knights are identical. We will now show that \( f(n) = g(n)/2. \) Label all squares of the \( n \times n \) board as \( S_1, S_2, \dots, S_{n^2} \) in any fixed order. Label the two distinct knights as \( N_1 \) and \( N_2. \) We represent each mutually attacking knight placement as an ordered pair \( (S_i, S_j) \) if \( N_1 \) is on \( S_i \) and \( N_2 \) is on \( S_j, \) with the two knights attacking each other. Here \( 1 \le i, j \le n^2 \) and \( i \ne j. \) Let \( M \) be the set of all mutually attacking knight placements for distinct knights on an \( n \times n \) board. Then \[ g(n) = \lvert M \rvert. \] If \( (S_i, S_j) \) is a mutually attacking knight placement of the distinct knights \( N_1 \) and \( N_2 \) for some \( i \) and \( j \) with \( 1 \le i, j \le n^2 \) and \( i \ne j, \) then \( (S_j, S_i) \) is also a mutually attacking knight placement, since swapping the positions of the two mutually attacking knights still yields a valid mutually attacking placement. Therefore \[ (S_i, S_j) \in M \iff (S_j, S_i) \in M. \] Each ordered placement \( (S_i, S_j) \) in \( M \) is thus paired with the ordered placement \( (S_j, S_i). \) When the knights are identical, the two arrangements are indistinguishable and count as one placement. Hence, the number of mutually attacking placements for identical knights is exactly half of the number for distinct knights, i.e. \[ f(n) = \frac{g(n)}{2}. \] The next subsection focuses on calculating \( g(n), \) from which \( f(n) \) follows immediately by the above formula. As noted in the previous section, the number of mutually attacking knight placements for two distinct knights on an \( n \times n \) board is simply the sum of attacking degrees of all squares on the board. If we label each square as discussed in the previous section and use the notation \( \deg(S_i) \) for the attacking degree of the square labelled \( S_i, \) where \( 1 \le i \le n^2, \) then \[ g(n) = \sum_{i=1}^{n^2} \deg(S_i). \] Recall that the attacking degree of a square is the number of squares a knight could attack if it were placed there. Earlier, we saw that on a \( 3 \times 3 \) board, all squares except the centre one have attacking degree \( 2, \) which gives \( g(3) = 8 \times 2 = 16 \) and \( f(3) = g(3)/2 = 8. \) Let us now write down the attacking degrees of all squares on a \( 4 \times 4 \) board. From the above illustration we get \begin{align*} g(4) & = 4 \times 2 + 8 \times 3 + 4 \times 4 = 48, \\ f(4) & = g(4)/2 = 24. \end{align*} A more general pattern emerges if we consider a larger board, such as a \( 6 \times 6 \) board. From this illustration, we get \begin{align*} g(6) & = 4 \times 2 + 8 \times 3 + 12 \times 4 + 8 \times 6 + 4 \times 8 = 160. \\ f(6) & = g(6)/2 = 80. \end{align*} Let us find a general formula now for \( n \ge 4. \) We introduce one more notation. Let \( D_k(n) \) denote the sum of the attacking degrees of all squares of attacking degree \( k \) on an \( n \times n \) board, i.e. \[ D_k(n) = \sum_{\mathclap{\deg(S_i) = k}} \deg(S_i). \] Since the only attacking degrees the squares can have are \( 2, 3, 4, 6 \) and \( 8, \) the sum of the attacking degrees of all squares can be written as \[ g(n) = D_2(n) + D_3(n) + D_4(n) + D_6(n) + D_8(n). \] There are exactly four squares of attacking degree \( 2. \) These are the corner ones. Therefore, \[ D_2(n) = 4 \times 2 = 8. \] The eight squares adjacent to the corner squares have attacking degree \( 3. \) Therefore, \[ D_3(n) = 8 \times 3 = 24. \] Let us define an inner corner square as one that shares a corner with a corner square but not an edge with it. There are four inner corner squares and each has attacking degree \( 4. \) Further, each row and column on the outer edge contains \( n - 4 \) additional squares with attacking degree \( 4. \) Therefore, \[ D_4(n) = (4 + 4(n - 4))(4) = 16(n - 3). \] Consider a row or column that contains two inner corner squares of attacking degree \( 4. \) All \( n - 4 \) squares between the inner corner squares have attacking degree \( 6. \) There are two such rows and two such columns. Therefore, \[ D_6(n) = 4(n - 4)(6) = 24(n - 4). \] We have counted the attacking degrees of all squares in the first two columns and rows as well as the last two columns and rows. We are left with \( (n - 4)^2 \) squares in the middle and they all have attacking degree \( 8. \) Therefore, \[ D_8(n) = 8(n - 4)^2. \] Therefore, \begin{align*} g(n) & = D_2(n) + D_3(n) + D_4(n) + D_6(n) + D_8(n) \\ & = 8 + 24 + 16(n - 3) + 24(n - 4) + 8(n - 4)^2 \\ & = 8(n - 1)(n - 2). \end{align*} Even though we assumed \( n \ge 4 \) while obtaining the above formula, remarkably, it gives us the correct values for \( n = 1, 2 \) and \( 3. \) The number of mutually attacking knight placements for distinct knights on an \( n \times n \) board is \( 0 \) if \( n = 1 \) or \( 2. \) It is \( 16 \) if \( n = 3. \) Indeed the above formula gives us \[ g(1) = g(2) = 0, \quad g(3) = 16. \] Therefore, we can now generalise the above result as \[ g(n) = 8(n - 1)(n - 2) \] for all \( n \ge 1. \) Therefore, for all \( n \ge 1, \) \[ f(n) = \frac{g(n)}{2} = 4(n - 1)(n - 2). \] Finally, in this section, we take a look at a simple and elegant solution that arrives at the closed-form solution in a more direct manner. The analysis begins by looking at the smallest section of the board where two knights can attack each other. Consider a \( 2 \times 3 \) section of a board of size \( 3 \times 3 \) or larger. Such a section has exactly two mutually attacking knight placements. Similarly, a \( 3 \times 2 \) section of a board also has exactly two mutually attacking knight placements. We call these \( 2 \times 3 \) and \( 3 \times 2 \) sections the minimal attack sections of a board, since no smaller section can contain a mutually attacking knight placement. Two distinct \( 2 \times 3 \) sections can share at most a \( 1 \times 3 \) section, which is smaller than a minimal attack section. Consequently, no mutually attacking knight placement can be common to two distinct \( 2 \times 3 \) sections of a board. Similarly, two distinct \( 3 \times 2 \) sections can share at most a \( 3 \times 1 \) section, again too small to contain a minimal attack section. Therefore, they share no mutually attacking knight placement. A \( 2 \times 3 \) section and a \( 3 \times 2 \) section can share at most a \( 2 \times 2 \) section, which is still smaller than a minimal attack section, so they share no mutually attacking knight placement either. To summarise, any two minimal attack sections of the board yield distinct pairs of mutually attacking knight placements. The total number of such placements is therefore exactly twice the number of minimal attack sections on the board. In an \( n \times n \) board where \( n \ge 3, \) the left edge of a \( 2 \times 3 \) section can be placed in any one of the first \( n - 2 \) columns of the board. Similarly, the top edge of such a section can be placed in any one of the first \( n - 1 \) rows of the board. Therefore, the total number of distinct \( 2 \times 3 \) sections on the board is \( (n - 2)(n - 1). \) By similar reasoning, the number of distinct \( 3 \times 2 \) sections on an \( n \times n \) board, where \( n \ge 3, \) is also \( (n - 1)(n - 2). \) Let \( h(n) \) be the total number of minimal attack sections we can find on an \( n \times n \) board where \( n \ge 1. \) From the discussion in the previous two paragraphs, we know that \( h(n) = 2(n - 1)(n - 2) \) for \( n \ge 3. \) Further, this formula for \( h(n) \) works for \( n = 1 \) and \( n = 2 \) as well since \( h(1) = h(2) = 0 \) and indeed a \( 1 \times 1 \) board or a \( 2 \times 2 \) board is too small to contain any minimal attack sections. Therefore, for all \( n \ge 1, \) we get \[ h(n) = 2(n - 1)(n - 2). \] Since each minimal attack section yields two mutually attacking knight placements, the total number of mutually attacking knight placements on an \( n \times n \) board is \[ f(n) = 2h(n) = 4(n - 1)(n - 2) \] for all \( n \ge 1. \) Read on website | #mathematics | #puzzle Introduction Counting Placements as the Board Grows Type A Squares Type B Squares Type C Squares Type D Squares Closed Form Expression Counting Placements for Each Square Attacking Degrees of Squares From Attacking Degrees to Counting Placements Closed Form Expression Counting Placements From Minimal Attack Sections Minimal Attack Sections Closed Form Expression Type A squares are the three new corner squares. Type B squares are the two new squares adjacent to type A squares at the top and left edges. Type C squares are the new squares that are not adjacent to any type A square. If the new board has dimensions \( n \times n, \) where \( n \ge 4, \) then there are exactly \( 2n - 8 \) squares of type C. Type D squares are the two new squares adjacent to the bottom-right type A square. Two Knights from the CSES Problem Set Knight Graph by Eric W. Weisstein OEIS Entry A033996 by N. J. A. Sloane OEIS Entry A172132 by Vaclav Kotesovec

programming Programming Mathematics Puzzle
0 views
Susam Pal 5 months ago

Zigzag Number Spiral

Consider the following infinite grid of numbers, where the numbers are arranged in a spiral-like manner, but the spiral reverses direction each time it reaches the edge of the grid: \begin{array}{rcrcrcrcrl} 1 & \rt & 2 & \sp & 9 & \rt & 10 & \sp & 25 & \cd \\ \sp & \sp & \dn & \sp & \up & \sp & \dn & \sp & \up & \sp \\ 4 & \lf & 3 & \sp & 8 & \sp & 11 & \sp & 24 & \cd \\ \dn & \sp & \sp & \sp & \up & \sp & \dn & \sp & \up & \sp \\ 5 & \rt & 6 & \rt & 7 & \sp & 12 & \sp & 23 & \cd \\ \sp & \sp & \sp & \sp & \sp & \sp & \dn & \sp & \up & \sp \\ 16 & \lf & 15 & \lf & 14 & \lf & 13 & \sp & 22 & \cd \\ \dn & \sp & \sp & \sp & \sp & \sp & \sp & \sp & \up & \sp \\ 17 & \rt & 18 & \rt & 19 & \rt & 20 & \rt & 21 & \cd \\ \vd & \sp & \vd & \sp & \vd & \sp & \vd & \sp & \vd & \dd \end{array} Can we find a closed-form expression that tells us the number at the \( m \)th row and \( n \)th column? Before we explore this problem further, let us rewrite the zigzag number spiral grid in a cleaner form, omitting the arrows: \begin{array}{rrrrrl} 1 & 2 & 9 & 10 & 25 & \cd \\ 4 & 3 & 8 & 11 & 24 & \cd \\ 5 & 6 & 7 & 12 & 23 & \cd \\ 16 & 15 & 14 & 13 & 22 & \cd \\ 17 & 18 & 19 & 20 & 21 & \cd \\ \vd & \vd & \vd & \vd & \vd & \dd \end{array} Let \( f(m, n) \) denote the number at the \( m \)th row and \( n \)th column. For example, \( f(1, 1) = 1 \) and \( f(2, 5) = 24. \) We want to find a closed-form expression for \( f(m, n). \) Let us first clarify what we mean by a closed-form expression . There is no universal definition of a closed-form expression, but the term typically refers to a mathematical expression involving variables and constants, built using a finite combination of basic operations: addition, subtraction, multiplication, division, integer exponents, roots with integer index and functions such as exponentials, logarithms and trigonometric functions. In this article, however, we need only addition, subtraction, division, squares and square roots. This may be a bit of a spoiler, but I must mention that the \( \max \) function appears in the closed-form expressions we are about to see. If you are concerned about whether functions like \( \max \) and \( \min \) are permitted in such expressions, note that \begin{align*} \max(m, n) & = \frac{m + n + \sqrt{(m - n)^2}}{2}, \\ \min(m, n) & = \frac{m + n - \sqrt{(m - n)^2}}{2}. \end{align*} So \( \max \) and \( \min \) are simply shorthand for expressions involving addition, subtraction, division, squares and square roots. In the discussion that follows, we will use only the \( \max \) function. Let us begin by analysing the edge numbers. Number the rows as \( 1, 2, 3 \dots \) and the columns likewise. Observe where the spiral touches the left edge and changes direction. This happens only on even-numbered rows. Similarly, each time the spiral touches the top edge and changes direction, it does so on odd-numbered columns. In the following subsections, we take a closer look at this behaviour of the spiral. I should mention that this section takes a rather long path to arrive at the closed-form solution. Personally, I enjoy such long tours. If you prefer a more direct approach, feel free to skip ahead to Patterns on the Diagonal for a shorter discussion that reaches the same result. Each time the spiral reaches the left edge of the grid, it does so at some \( m \)th row where \( m \) is even. The \( m \times m \) subgrid formed by the first \( m \) rows and the first \( m \) columns contains \( m^2 \) consecutive numbers. Since the numbers strictly increase as the spiral grows, the largest of these \( m^2 \) numbers must appear at the position where the spiral touches the left edge. This is illustrated in the figure below. Whenever the spiral touches the left edge at the \( m \)th row (where \( m \) is even), the number in the first column of that row is \( m^2. \) Hence, we conclude that \( f(m, 1) = m^2 \) when \( m \) is even. Immediately after touching the left edge, the spiral turns downwards into the first column of the next row. Thus, in the next row, i.e. in the \( (m + 1) \)th row, we have \( f(m + 1, 1) = m^2 + 1, \) where \( m + 1 \) is odd. This can be restated as \( f(m, 1) = (m - 1)^2 + 1 \) when \( m \) is odd. Since \( f(1, 1) = 1, \) we can summarise the two formulas we have found here as: \[ f(m, 1) = \begin{cases} m^2 & \text{if } m \equiv 0 \pmod{2}, \\ (m - 1)^2 + 1 & \text{if } m \equiv 1 \pmod{2}. \end{cases} \] We can perform a similar analysis for the numbers at the top edge and note that whenever the spiral touches the top edge at the \( n \)th column (where \( n \) is odd), the number in the first row of that column is \( n^2. \) This is illustrated below. Immediately after touching the top edge, the spiral turns right into the next column. These observations give us the following formula for the numbers at the top edge: \[ f(1, n) = \begin{cases} n^2 & \text{if } n \equiv 1 \pmod{2}, \\ (n - 1)^2 + 1 & \text{if } n \equiv 0 \pmod{2}. \end{cases} \] Next we will find a formula for any arbitrary number anywhere in the grid. Since the spiral touches the left edge on even-numbered rows, then turns downwards into the next (odd-numbered) row and then starts moving right until the diagonal (where it changes direction again), the following two rules hold: Note that all the numbers we considered in the above two points lie on or below the diagonal (or equivalently, on or to the left of the diagonal). Therefore, on an odd-numbered row, we can find the numbers on or below the diagonal using the formula \( f(m, n) = f(m, 1) + (n - 1), \) where \( m \) is odd. Similarly, on even-numbered rows, we can find the numbers on or below the diagonal using the formula \( f(m, n) = f(m, 1) - (n - 1), \) where \( m \) is even. By a similar analysis, the following rules hold when we consider the numbers in a column: Now the numbers on or above the diagonal can be found using the formula \( f(m, n) = f(1, n) - (m - 1) \) when \( n \) is odd and \( f(m, n) = f(1, n) + (m - 1), \) when \( n \) is even. Can we determine from the values of \( m \) and \( n \) if the number \( f(m, n) \) is above the diagonal or below it? Yes, if \( m \le n, \) then \( f(m, n) \) lies on or above the diagonal. However, if \( m \ge n, \) then \( f(m, n) \) lies on or below the diagonal. We now have everything we need to write a general formula for finding the numbers anywhere in the grid. Using the four formulas and the two inequalities obtained in this section, we get \[ f(m, n) = \begin{cases} f(1, n) + (m - 1) & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ f(1, n) - (m - 1) & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ f(m, 1) - (n - 1) & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ f(m, 1) + (n - 1) & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] Using the equations for \( f(1, n) \) and \( f(m, 1) \) from the previous section, the above formulas can be rewritten as \[ f(m, n) = \begin{cases} (n - 1)^2 + 1 + (m - 1) & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ n^2 - (m - 1) & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ m^2 - (n - 1) & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ (m - 1)^2 + 1 + (n - 1) & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] Simplifying the expressions on the right-hand side, we get \[ f(m, n) = \begin{cases} (n - 1)^2 + m & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ n^2 - m + 1 & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ m^2 - n + 1 & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ (m - 1)^2 + n & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] This is pretty good. We now have a piecewise formula that works for any position in the grid. Let us now explore whether we can express it as a single closed-form expression. First, we will rewrite the piecewise formula from the previous section in the following form: \[ f(m, n) = \begin{cases} (n^2 - n + 1) + (m - n) & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ (n^2 - n + 1) - (m - n) & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ (m^2 - m + 1) + (m - n) & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ (m^2 - m + 1) - (m - n) & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] This is the same formula, rewritten to reveal common patterns between the four expressions on the right-hand side. In each expression, one variable plays the dominant role, occurring several times, while the other appears only once. For example, in the first two expressions, \( n \) plays the dominant role whereas \( m \) occurs only once. If we look closely, we realise that it is the variable that is greater than or equal to the other that plays the dominant role. Therefore the first and third expressions may be written as \[ \left( (\max(m, n))^2 - \max(m, n) + 1 \right) + (m - n). \] Similarly, the second and fourth expressions may be written as \[ \left( (\max(m, n))^2 - \max(m, n) + 1 \right) - (m - n). \] We have made some progress towards a closed-form expression. We have collapsed the four expressions in the piecewise formula to just two. The only difference between them lies in the sign of the second term: it is positive when the dominant variable is even and negative when it is odd. This observation allows us to unify both cases into a single expression: \[ f(m, n) = (\max(m, n))^2 - \max(m, n) + 1 + (-1)^{\max(m, n)} (m - n). \] Now we have a closed-form expression for \( f(m, n) \) that gives the number at any position in the grid. As mentioned earlier, there is a shorter route to the same closed-form expression. This alternative approach is based on analysing the numbers along the diagonal of the grid. We still need to examine the edge numbers, but not all of them as we did in the previous section. Some of the reasoning about edge values will be repeated here to ensure this section is self-contained. A number on the diagonal has the same row number and column number. In other words, a diagonal number has the value \( f(n, n) \) for some positive integer \( n. \) Consider the case when \( n \) is even. In this case, the diagonal number is on a segment of the spiral that is moving to the left. The \( n \times n \) subgrid formed by the first \( n \) rows and the first \( n \) columns contains exactly \( n^2 \) consecutive numbers. Since the diagonal number is on the last row of this subgrid and the numbers in this row increase as we move from right to left, the largest number in the subgrid must be on the left edge of this row. Therefore the number at the left edge is \( f(n, 1) = n^2, \) where \( n \) is even. This is illustrated below. From the diagonal to the edge of the subgrid, there are \( n \) consecutive numbers. In a sequence of \( n \) consecutive numbers, the difference between the maximum number and the minimum number is \( n - 1. \) Therefore, \( n^2 - f(n, n) = n - 1. \) This gives us \[ f(n, n) = n^2 - n + 1 \quad \text{if } n \equiv 0 \pmod{2}. \] Now consider the case when \( n \) is odd. By a similar reasoning, for odd \( n, \) the \( n \)th column has numbers that increase as we move up from the diagonal number towards the top edge. Therefore \( f(1, n) = n^2 \) and since \( n^2 - f(n, n) = n - 1, \) we again obtain \[ f(n, n) = n^2 - n + 1 \quad \text{if } n \equiv 1 \pmod{2}. \] Since \( f(n, n) \) takes the same form for both odd and even \( n, \) we can write \[ f(n, n) = n^2 - n + 1 \] for all positive integers \( n. \) If \( m \le n, \) then the number \( f(m, n) \) lies on or above the diagonal number \( f(n, n). \) If \( n \) is even, then the numbers decrease as we go from the diagonal up to the top edge. Therefore \( f(m, n) \le f(n, n) \) and \( f(m, n) = f(n, n) - (n - m). \) If \( n \) is odd, then the numbers increase as we go from the diagonal up to the top edge and therefore \( f(m, n) \ge f(n, n) \) and \( f(m, n) = f(n, n) + (n - m). \) If \( m \ge n, \) then the number \( f(m, n) \) lies on or below the diagonal number \( f(m, m). \) By a similar analysis, we find that \( f(m, n) = f(m, m) + (m - n) \) if \( n \) is even and \( f(m, n) = f(m, m) - (m - n) \) if \( n \) is odd. We summarise these results as follows: \[ f(m, n) = \begin{cases} f(n, n) - (n - m) & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ f(n, n) + (n - m) & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ f(m, m) + (m - n) & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ f(m, m) - (m - n) & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] Note that the above formula can be rewritten as \[ f(m, n) = \begin{cases} f(n, n) + (m - n) & \text{if } m \le n \text{ and } n \equiv 0 \pmod{2}, \\ f(n, n) - (m - n) & \text{if } m \le n \text{ and } n \equiv 1 \pmod{2}, \\ f(m, m) + (m - n) & \text{if } m \ge n \text{ and } m \equiv 0 \pmod{2}, \\ f(m, m) - (m - n) & \text{if } m \ge n \text{ and } m \equiv 1 \pmod{2}. \\ \end{cases} \] If we take a close look at the last formula in the previous section, we find that in each expression, one variable plays a dominant role, i.e. it occurs more frequently in the expression than the other. In the first two expressions \( n \) plays the dominant role whereas in the last two expressions \( m \) plays the dominant role. In fact, in each expression, the dominant variable is the one that is greater than or equal to the other. With this in mind, we can rewrite the above formula as \[ f(m, n) = \begin{cases} f(\max(m, n), \max(m, n)) + (m - n) & \text{if } \max(m, n) \equiv 0 \pmod{2}, \\ f(\max(m, n), \max(m, n)) - (m - n) & \text{if } \max(m, n) \equiv 1 \pmod{2}. \\ \end{cases} \] The only difference between the expressions is the sign of the second term: it is positive when \( \max(m, n) \) is even and negative when \( \max(m, n) \) is odd. As a result, we can rewrite the above formula as a single expression like this: \[ f(m, n) = f(\max(m, n), \max(m, n)) + (-1)^{\max(m, n)} (m - n). \] Using the formula \( f(n, n) = n^2 - n + 1 \) from the previous section, we get \[ f(m, n) = (\max(m, n))^2 - \max(m, n) + 1 + (-1)^{\max(m, n)} (m - n). \] We arrive again at the same closed-form expression, this time by focusing on the diagonal of the grid. Read on website | #mathematics | #puzzle Introduction Patterns on the Edges Computing Edge Numbers Computing All Grid Numbers Closed Form Expression Patterns on the Diagonal Computing Diagonal Numbers Computing All Grid Numbers Closed Form Expression On every odd-numbered row, as we go from left to right, the numbers increase until we reach the diagonal. On every even-numbered row, as we go from left to right, the numbers decrease until we reach the diagonal. On every even-numbered column, as we go from top to bottom, the numbers increase until we reach the diagonal. On every odd-numbered column, as we go from top to bottom, the numbers decrease until we reach the diagonal. Number Spiral from the CSES Problem Set Closed-Form Solution by Christopher Stover and Eric W. Weisstein Piecewise Function by Eric W. Weisstein

programming Programming Mathematics
0 views