Florian Galliot

Sylvain Gravier

Isabelle Sivignon

An update on the coin-moving game on the square grid

Introduction

We study a one-player game that is played on an undirected simple graph G = (V, E), referred to as the game graph or board. Throughout the game, there will be coins sitting on some of the vertices of G (at most one per vertex). The coins are indistinguishable and define a configuration, i.e. a finite subset C ⊆ V where we see each element of C as a coin sitting on the corresponding vertex. A legal move consists in moving a single coin to a free vertex so that, after the move, that coin has at least two other coins adjacent to it. This is called the 2-adjacency restriction. Given two configurations A and B, we want to know whether the puzzle A ? -→ B is solvable: starting from A, is it possible to reach B using only legal moves? In the positive case, we would like an explicit winning sequence of moves. This game falls into the category of reconfiguration problems on graphs.

Instances of this game, or rather a variation with tightly packed coins that can only be slid in the plane without collision, appear in the literature as early as the 1950s in [START_REF] Langman | Curiosa 261: A disc puzzle[END_REF] and [START_REF] Langman | Curiosa 342: Easy but not obvious[END_REF]. Figure 1 features a couple of classic puzzles on the triangular grid as well as a more rare puzzle on the square grid. Such examples also appear in [START_REF] Gardner | Mathematical Carnival, chapter 2 "Penny Puzzles[END_REF] and [BCG82] among others, but it is not until 2002 that general puzzles with these rules have been studied, in [START_REF] Demaine | Coin-Moving Puzzles[END_REF] which serves as foundation for the present paper. The authors give a full characterization for solvable puzzles on the triangular grid (up to a minor omission which is easily settled: see [START_REF] Galliot | A coin-moving game on graphs[END_REF]). Furthermore, they address a large family of puzzles on the square grid, providing polynomial time solving algorithms. Another coin-moving game on the square grid, with different rules but similar methods and also polynomial time algorithms in many cases, is studied in [START_REF] Dumitrescu | Pushing squares around[END_REF].

?

? ?

Figure 1. The game graph is the triangular grid in the left and middle puzzles, and the square grid in the right puzzle. The left (resp. middle, resp. right) puzzle is solvable in 2 (resp. 3, resp. 4) moves.

In this paper, we exclusively study the case where G is the square grid (each vertex has four neighbours: left, right, top, bottom). A first natural question is : what can we reach starting from a configuration A? A central observation is that, during the moves, all coins remain inside of the span of A, which is a finite set (union of rectangles) obtained from A by including all vertices that have at least two neighbours in A and iterating this process until no more vertex can be included. Any configuration B that we wish to obtain from A must therefore satisfy B ⊆ span(A), which implies span(B) ⊆ span(A). In the study that is made in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], a key information is the number of coins that can be removed from A while maintaining a span containing that of B: we call them extra coins in A relatively to B. The more extra coins at our disposal, the more flexibility with respect to the span constraint, hence, the easier a puzzle. Section 1 goes over fundamental observations and notions introduced in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], including that of span and extra coins, with the addition of some basic results of our own that will be used in this paper. Section 2 then recalls the method that is employed to solve puzzles in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], which we will also use ourselves.

In [START_REF] Demaine | Coin-Moving Puzzles[END_REF], the authors claim that, up to an additional condition on B, two extra coins in A relatively to B are enough to solve any puzzle. Unfortunately, the proof only works if A and B have the same span. In Section 3, we extend this result to the case where each connected component of span(A) contains at most one connected component of span (B).

If this latter condition is not satisfied however, then Section 4 provides, for any n, an example of an unsolvable puzzle where the span of A is an n × n square and A has about n 2 extra coins relatively to B (with B satisfying the additional condition from [START_REF] Demaine | Coin-Moving Puzzles[END_REF], and some more). It is worth noticing that n, in that case, is also the minimum cardinality of a configuration having anjk n × n span. We then give a new sufficient condition for a puzzle to be solvable, which shows in particular that this number n 2 is somehow tight. As mentioned in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], the case of a single extra coin is even more complicated. The first non-trivial results for this case are presented in Section 5, under the restriction that A and B have the same span and contain exactly one coin (the extra coin) more than the minimum possible for their span. We show that our game then reduces to a poking game where, instead of the 2-adjacency rule, a coin can be slid onto a neighbouring vertex under certain conditions. We give necessary and sufficient conditions for poking puzzles involving what is called a chain of coins.

Preliminaries

Notations and first observations

We use the (self-)dual grid for graphical representations of the game: each vertex, or position, is seen as a square and coins are placed at the center of squares.

Notation 1.1. We introduce the following notations:

• Moving a coin c to a valid destination p is denoted by c → p. Note that a coin c is simply an element of V representing its location (since the coins are indistinguishable, a coin c is nothing but an occupied position p). Typically, the notation c is used to designate an occupied position, and the notation p is used for a position that is either unoccupied or not necessarily occupied. • If there is a single move c → p from A to B, we write A

Proof. Suppose that

A = A 0 c 1 →p 1 ----→ A 1 c 2 →p 2 ----→ . . .
T -1 = c T , p T -2 = c T -1 , . . . , p 1 = c 2 .
In conclusion, we have moved the same coin each time, so we could have moved it just once instead and got A

c 1 →p T ----→ B.

Picking up and dropping coins

Definition 1.4. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] Consider the following actions:

• Pick up a coin: remove a coin from the board, without any restriction on its position.

• Drop a coin: put a previously picked up coin back on the board, with the 2-adjacency restriction. Picked up coins that have not yet been dropped may be referred to as coins in hand.

It is shown in [START_REF] Demaine | Coin-Moving Puzzles[END_REF] that the game is unchanged if the player is allowed to pick up and drop coins additionally to moving them: Proposition 1.5. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] A puzzle is solvable (by moving coins) if and only if it is solvable by moving, picking up and dropping coins.

Notation 1.6. In this variation, the state of the game at any given moment is described by the configuration A on board and the number k of coins in hand: we denote this information by A +k . For example, the notation A +k → B +k means that, from the configuration A with k coins in hand at the start, it is possible (via moving, picking up and dropping coins) to reach the configuration B with k = k + |A| -|B| coins in hand at the end.

Span of a configuration

As mentioned in the introduction, the notion of span is central to the study of the game on the square grid.

Notation 1.7. Let C be a configuration, we denote by Adj(C) ⊆ V \ C the set of all positions outside C that have at least two neighbours in C. Definition 1.8. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] The span of a configuration C, denoted by span(C), is the limit of the non-decreasing sequence of configurations (C i ) i≥0 defined recursively by C 0 = C and

C i+1 = C i ∪ Adj(C i ).
In other words, span(C) is the set of all positions that could be reached from C if we had unlimited coins to add to the board at successive positions satisfying the 2-adjacency rule.

Proposition 1.9. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] The span never increases during moves: if A → B then span(A) ⊇ span(B).

Definition 1.10. Identifying the square grid as Z 2 , an m × n rectangle R is a set of positions of the form I × J where I and J are intervals of cardinality m and n respectively, so that each row of R contains m positions and each column of R contains n positions. We say R is even (resp. odd) if its half-perimeter m + n is even (resp. odd).

Proposition 1.11. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] The span of any configuration C is a union of rectangles at distance at least 3 from each other (these rectangles are called the components of span(C)).

An example can be seen in Figure 3. We add the following elementary property of the span which will be useful later.

Figure 3.

The span of a configuration. In this example, there are four components.

Proposition 1.12. Let C be a configuration and let R be a component of span(C). Then C contains at least one coin in each of the following: the top row of R, the bottom row of R, the leftmost column of R, the rightmost column of R, any union of two consecutive rows in R, any union of two consecutive columns in R.

Proof. Using the symmetries, we only address the case of the top row and the union of two consecutive rows. Let C = C 0 , C 1 , . . . , C s = span(C) as in Definition 1.8 (indeed, the sequence (C i ) i≥0 is stationary by finiteness of the span).

• Suppose for a contradiction that the top row R contains no coin in C i.e. C ∩ R = ∅. Let i ∈ {0, . . . , s} be smallest such that

C i ∩ R = ∅: we have i ≥ 1 and C i-1 ∩ R = ∅. Obviously, any position in R has at most one neighbour in R \ R , so Adj(C i-1 ) ∩ R = ∅. Since C i = C i-1 ∪ Adj(C i-1 ), we get C i ∩ R = ∅ which is a contradiction. •
The previous proof still works if we replace R by any union of two consecutive rows, since the key argument that any position in R has at most one neighbour in R \ R still holds. Proposition 1.14. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] Any move played from a minimal configuration decreases the span.

Minimal/minimum configurations

As noticed in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], the cardinality of minimum configurations (as well as a lot of information on their structure) is well known thanks to the following classic problem from folklore. In a rectangular parcel R consisting of small squares arranged in a grid, some squares are initially invaded by weeds. Time passes, and at each time step, any square that is adjacent to at least two weeds-covered squares gets invaded in turn. How many squares need to be covered initially for the entire parcel to be invaded in the end? Since the rule for the propagation of the weeds is exactly the same as for the construction of the span, the answer coincides with the cardinality of a minimum configuration with span R. This problem was first published in [START_REF]Problems from the 49th Moscow Mathematical Olympiad[END_REF] for a 10 × 10 parcel. An elegant solution is obtained via an invariant which is the perimeter of the invaded area: . Conversely, it is easy to find configurations with span R that have exactly m+n 2 coins (think of a diagonal of coins if m = n, or more generally an 'L' shape as in Definition 2.4), so the cardinality of minimum configurations with span R is exactly m+n 2 . Finally, let M be a minimum configuration with span R and let l be the number of pairs of adjacent coins in M , we have 2(m + n) ≤ Perim(M ) = 4 m+n 2 -2l, so in conclusion:

• If R is even, then 2(m + n) ≤ 4 m+n 2 -2l hence l = 0 i.e. all coins in M are isolated.

• If R is odd, then 2(m + n) ≤ 4 m+n+1 2 -2l hence l ∈ {0, 1} i.e.
all coins in M are isolated except possibly for a single pair of adjacent coins.

Extra coins and redundant coins

We recall the notion of extra coins defined in the introduction: Proof. Suppose A does not have one extra coin relatively to B, and consider the first move c → p made from A. This move can be decomposed as follows: first we remove c from the board, then we put it back at p. After removing c from the board, the span is span(A \ {c}). When we put the coin back, the span stays the same because of the 2-adjacency rule. Therefore the span after the first move is span(A \ {c}), which does not contain span(B) because {c} is not a set of extra coins relatively to B. By Proposition 1.9, the span cannot increase during the moves, hence A → B.

We now introduce the notion of redundant coins, which is also present in [START_REF] Demaine | Coin-Moving Puzzles[END_REF]

For example, in the puzzle

A ? - → B from Figure 4, {b 1 , b 2 } is a set of redundant coins in B.
Note that redundant coins are extra coins, but the converse is not true in general (think of a 1 and a 2 in Figure 4). Therefore, more redundant coins can only make a puzzle easier. One can think of extra coins in A (or extra coins in A relatively to B) as the first coins that we move, and of redundant coins in B as the last coins that we place.

Canonical configurations

In [START_REF] Demaine | Coin-Moving Puzzles[END_REF], the authors define a reference minimum configuration for a given span, called the canonical configuration. Their method to solve a puzzle A ? -→ B, if span(A) = span(B) for instance, consists in going from A to B by routing through their common canonical configuration. We will reuse this principle in Sections 3, 4 and 5. This section provides a summary of the definitions and results about canonical configurations that are presented in [START_REF] Demaine | Coin-Moving Puzzles[END_REF].

Definitions

Notation 2.1. We denote by dist the usual distance in the square grid.

Definition 2.2. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] A chain between some coins c and c is the configuration denoted by [c 1 , . . . , c N ] which is formed by a sequence of coins (c = c 1 , c 2 , . . . , c N = c ) such that dist(c i , c i+1 ) ∈ {1, 2} for all i ∈ {1, . . . , N -1}.

Proposition 2.3. [DDV02]

The span of a chain coincides with its smallest enclosing rectangle. Definition 2.4. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] An 'L' of size m × n is a minimum chain L between two opposite corners of an m × n rectangle R and hugging two consecutive sides of R. We say L is even (resp. odd) if R is even (resp. odd) i.e. if m + n is even (resp. odd). See Figure 5 (right).

In accordance with Proposition 1.15, an m × n 'L' has cardinality m+n 2 , and consecutive coins in an even 'L' are at distance exactly 2 whereas consecutive coins in an odd 'L' are at distance exactly 2 except for a single pair of adjacent coins. An even 'L' is entirely defined by its span and orientation, whereas for an odd 'L' we also need the localisation of the two adjacent coins. By Proposition 2.3, the span of an 'L' is its smallest enclosing rectangle i.e. R in Definition 2.4. Definition 2.5. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] Let R be an m × n rectangle: the canonical 'L' with span R is the 'L' with span R that is oriented like the letter L, with the additional property if R is odd that the two adjacent coins are in the top-left corner (if n is even) or bottom-right corner (if m is even). Let C be a configuration with span s i=1 R i where R 1 , . . . , R s are rectangles at distance at least 3 from each other, as per Proposition 1.11: the canonical configuration associated to C is the configuration denoted by L C with same span as C such that L C ∩ R i is the canonical 'L' with span R i . See Figure 5.

Transformations of 'L's

Transformations of 'L's are the main subroutines used in the solving algorithms from [START_REF] Demaine | Coin-Moving Puzzles[END_REF]. We have the following: Proposition 2.6. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] Let L 1 and L 2 be two 'L's with same span. Then

L +2 1 ↔ L +2 2 .
In particular, two coins in hand are enough to flip any 'L', which means turning it into the mirrored 'L' hugging the other two sides of the span. Let us introduce our own routines for this particular transformation, one reason being that our method to flip odd 'L's only uses one extra coin, which will be useful in Section 5. Figure 7 explains how to flip an even 'L' with two coins in hand, using the subroutines from Figure 6. Figure 10 explains how to flip an even 'L' with one coin in hand, using the subroutines from Figure 9 as well as the leapfrog technique described in Figure 8: a leapfrog means relocating the unique pair of adjacent coins inside of an odd 'L'. In all figures throughout this paper, an encircled coin represents a coin that has just been dropped, while a crossed out coin represents a coin that we pick up.

Canonicalization process

The crucial result is that two coins in hand are enough to turn any configuration into its associated canonical configuration in a reversible manner:

Lemma 2.7. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] For any configuration C, we have From there, a method to solve a puzzle A ? -→ B would roughly be to: pick up two coins in A; canonicalize; reverse into B minus two coins; drop two coins to finish B. To do this however:

C +2 ↔ L +2+|C|-|L C | C .
-We need two coins in A that we can pick up without breaking the inclusion of spans at the start i.e. 2 extra coins in A relatively to B. -We need two appropriate spots in B to drop our two coins in hand at the end i.e. 2 redundant coins in B. Moreover, unless the spans are equal once the first two coins {a 1 , a 2 } have been picked up, we need a way to go from L A\{a 1 ,a 2 } to L B . This reasoning can be summed up as follows:

Corollary 2.8. Let A and B be configurations such that |A| = |B| and:

(i) A has 2 extra coins relatively to B.

(ii) B has 2 redundant coins.

Let A 0 := A \ {a 1 , a 2 } where {a 1 , a 2 } is a set of extra coins in A relatively to B. If L +|A|-|L A 0 | A 0 → L +|B|-|L B | B , then A → B. Proof. Let B 0 := B \{b 1 , b 2 } where {b 1 , b 2 } is a set of redundant coins in B. Note that L B = L B 0 since span(B) = span(B 0 ). We go from A to B in five steps: • We get A → A +2
0 by picking up a 1 and a 2 .

• Lemma 2.7 ensures that

A +2 0 → L +2+|A 0 |-|L A 0 | A 0 . • We have L +2+|A 0 |-|L A 0 | A 0 = L +|A|-|L A 0 | A 0 → L +|B|-|L B | B = L +2+|B 0 |-|L B 0 | B 0
by assumption.

• Lemma 2.7 ensures that L

+2+|B 0 |-|L B 0 | B 0 → B +2 0 .
• Finally, Proposition 1.20 yields

B +2 0 → B.
3 Two extra coins: with additional constraints

In [START_REF] Demaine | Coin-Moving Puzzles[END_REF], the authors studied the case where A has 2 extra coins relatively to B, which seemed enough to solve most puzzles. In this section, we go back on their result and then give it a slight improvement.

Previous result

The main result in [START_REF] Demaine | Coin-Moving Puzzles[END_REF] is the following:

Theorem 3.1. [START_REF] Demaine | Coin-Moving Puzzles[END_REF] Let A and B be configurations such that |A| = |B|, and suppose that:

(i) span(A) = span(B). (ii) A has 2 extra coins relatively to B. (iii) B has 2 redundant coins. Then A → B.
As mentioned in Section 2, this theorem uses canonical configurations as an intermediary. Indeed, it follows immediately from Corollary 2.8 (with

L A 0 = L A = L B since span(A) = span(B)
). An example of a puzzle that is solvable according to Theorem 3.1 is the one in Figure 4, where

{a 1 , a 2 } is a set of extra coins in A relatively to B and {b 1 , b 2 } is a set of redundant coins in B.
In fact, a stronger version of this theorem is claimed in [START_REF] Demaine | Coin-Moving Puzzles[END_REF], where condition (i) is not required. The authors reduce to the case where span(A) = span(B) by picking up all coins in A \ span(B). However, this does not work in general, because this might actually cause the span to become strictly smaller than that of B. It turns out that, without the added condition (i), some puzzles are solvable and some are not, as illustrated by Figure 11. The puzzle on the left is solvable in 12 moves. The puzzle on the right is unsolvable (as we will later prove) and therefore is a counterexample to the version of the theorem in [START_REF] Demaine | Coin-Moving Puzzles[END_REF]. It is easy to check that no smaller counterexample exists, be it in terms of number of coins or half-perimeter of the starting span. A generalized family of counterexamples will be exhibited in Section 4: in all of them, the problem comes from the fact that span(B) is split into two far apart components.

? ?

Figure 11. Two puzzles satisfying conditions (ii) and (iii) but not (i), since span(A) span(B). The left one is solvable but the right one is not.

A slight improvement

First of all, we show that Theorem 3.1 can be slightly improved: instead of asking for the spans to be equal, it is sufficient that each component of the starting span contains at most one component of the target span. Indeed, while splitting an 'L' into two separate components can be difficult (as we have just seen), shrinking an 'L' with two coins in hand is not a problem.

Lemma 3.2. If L 1 and L 2 are canonical 'L's with span(L 1 ) ⊇ span(L 2 ), then L +2 1 → L +2+|L 1 |-|L 2 | 2 .
Proof. First of all, we trim L 1 to the right if needed, as follows (see Figure 12): 1. If L 1 is odd, we use a leapfrog to put the pair of adjacent coins to the far right. 2. We make sure there is a coin c at the rightmost position that we want to keep, by dropping one there if needed. 3. We finish by simply picking up all coins that are further right than c. We then trim our 'L' at the top, in analogous fashion. We now flip it, so it is now ready to be trimmed to the left and at the bottom. Once this is done, we flip it back and use a leapfrog if needed to make it canonical. Note that puzzles satisfying condition (i) but not condition (ii) (while still satisfying the fact that B has 1 redundant coin, otherwise we would be in a trivially unsolvable case by Proposition 1.19) also may or may not be solvable as shown in Figure 13.

Two extra coins: general case

What if some component of span(A) contains two or more components of span(B), so that Theorem 3.3 does not apply? A first natural guess would be that we then need more extra coins and/or more redundant coins than just two. Nevertheless, we now exhibit a family of unsolvable puzzles which proves that, even with the inclusion of spans, no constant number of extra coins in A (relatively to B or not) or redundant coins in B can guarantee that a puzzle is solvable in general. Next, we present a new sufficient condition, which shows in particular that the aforementioned family consists of just about worst-case puzzles.

Worst-case puzzles

Puzzles like those from Figure 11 require to split the span, at some point during the moves, in a way that we now prove impossible without a certain amount of total coins relative to the size of the rectangles involved.

Definition 4.1. Let R 1 and R 2 be rectangles at distance at least 3 from each other, and let A be a configuration such that R 1 and R 2 are included in the same component of span(A). An

(R 1 , R 2 )-split of A is a sequence of moves A = A 0 → A 1 → . . . → A T (T ≥ 1 necessarily) such that R 1 and R 2 are included in two separate components of span(A T ).
Proposition 4.2. Let R 1 and R 2 be rectangles of size m 1 × n 1 and m 2 × n 2 respectively, whose projections on the x axis intersect, and whose projections on the y axis do not intersect with a gap of h ≥ 2 rows separating them. Let A be a configuration such that R 1 and R 2 are included in the same component of span(A). If there exists an (R 1 , R 2 )-split of A, then |A| ≥ m 1 +n 1 +m 2 +n 2 +h-1 2 .

Proof. Let A = A 0 → A 1 → . . . → A T be an (R 1 , R 2 )-split of A with minimum number of moves, so that R 1 and R 2 are included in the same component R of span(A T -1 ) but in two separate components R 1 and R 2 of span(A T ) (see Figure 14). If R 1 is of size m 1 × n 1 and R 2 is of size m 2 × n 2 with a gap of h rows separating them, then we have

m 1 ≥ m 1 , m 2 ≥ m 2 and n 1 + n 2 + h ≥ n 1 + n 2 + h hence m 1 +n 1 +m 2 +n 2 +h -1 2 ≥ m 1 +n 1 +m 2 +n 2 +h-1 2
. Therefore, the worst case for what we want to prove is if R 1 = R 1 and R 2 = R 2 , which is what we assume from now.

n 1 n ′ 1 n 2 n ′ 2 h ′ h m 2 m ′ 2 m 1 m ′ 1 R R ′ 1 R ′ 2 R 1 R 2 Figure 14. Illustration of R, R 1 , R 2 , R 1 , R 2 .
We use A T -1 to count the coins and carry out the proof. We have:

|A| = |A T -1 | = |A T -1 ∩ R 1 | + |A T -1 ∩ R 2 | + |A T -1 \ (R 1 ∪ R 2 )|. (1)
Moreover:

• The only coin in A T ∩ R 1 that might not be in A T -1 ∩ R 1 is the coin that has been moved to go from A T -1 to A T , however that coin does not contribute to the span since it has at least two coins adjacent to it in

A T ∩ R 1 . Since span(A T ∩ R 1 ) = R 1 , we thus get span(A T -1 ∩ R 1 ) = R 1 .
In particular, Proposition 1.15 yields:

|A T -1 ∩ R 1 | ≥ m 1 + n 1 2 . ( 2
)
• Similarly, span(A T -1 ∩ R 2 ) = R 2 and:

|A T -1 ∩ R 2 | ≥ m 2 + n 2 2 . ( 3
)
• By Proposition 1.12, there cannot be two consecutive rows of R without a coin in A T -1 . Since there is a gap of h rows between R 1 and R 2 , this yields:

|A T -1 \ (R 1 ∪ R 2 )| ≥ h 2 . ( 4
)
Combining (1), (2), (3) and (4), we get: Proof. Let R 1 (resp. R 2 ) be the top row (resp. the bottom row) of span(A n ): R 1 and R 2 are of size n × 1 and separated by a gap of n -2 rows. Solving this puzzle would mean performing an (R 1 , R 2 )-split of A n , which is impossible by Proposition 4.2 because:

|A| ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 ≥ m 1 + n 1 + m 2 + n 2 + h -1 2 . ? A n B n
• If n is odd then n + n-3 2 = |A n | = |B n | = 2 n+1 2 + n-5 2 = 3n-3 2 < n+1+n+1+(n-2)-1 2 . • If n is even then n + n-2 2 = |A n | = |B n | = 2 n+2 2 + n-6 2 = 3n-2 2 < n+1+n+1+(n-2)-1 2 .
Corollary 4.4. For any k ∈ N, there exist configurations A and B with |A| = |B| such that:

• span(A) ⊃ span(B). • A has k extra coins. • B has k redundant coins. • A → B.
It is actually possible to improve Proposition 4.2: we now give a refined bound that even applies to the puzzle on the right of Figure 11 which, as previously mentioned, is the smallest counterexample to the version of Theorem 3.1 in [START_REF] Demaine | Coin-Moving Puzzles[END_REF].

Proposition 4.5. Let R 1 , R 2 and A be as in Proposition 4.2. If there exists an (R 1 , R 2 )-split of A but none in two moves or less, then |A| ≥ m 1 +n 1 +m 2 +n 2 +h+2 2 .

Proof. Let us pick up where the proof of Proposition 4.2 ended. Since there exists no (R 1 , R 2 )split of A in two moves or less, we have T ≥ 3. We use the fact that A T -1 then has the following properties: (i) A T -1 contains a coin that is adjacent to at least two other coins.

(ii) For all c ∈ A T -1 , A T -1 \ {c} does not consist of all isolated coins. Property (i) comes from Proposition 1.2 since T -1 ≥ 1, and property (ii) comes from Proposition 1.3 since T -1 ≥ 2 (indeed A → A T -1 because our sequence of moves has been chosen shortest). We distinguish between four cases: 1) Case 1: R 1 and R 2 are both odd; h is even. This is the easiest case:

|A| ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 = m 1 + n 1 + 1 2 + m 2 + n 2 + 1 2 + h 2 = m 1 + n 1 + m 2 + n 2 + h + 2 2 .
2) Case 2: At least one of R 1 or R 2 is even (say R 2 is even); h is even. We just need to find one coin more than what (2), (3) and (4) give us combined, because if we do then we can conclude that:

|A| ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 + 1 ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 + 1 = m 1 + n 1 + m 2 + n 2 + h + 2 2 .
Therefore, suppose for a contradiction that (2), (3) and ( 4) are all tight. For (4), this means that A T -1 \ (R 1 ∪ R 2 ) consists exactly of one coin every two rows in the gap between R 1 and R 2 . For (2) and (3), this means

A T -1 ∩ R 1 and A T -1 ∩ R 2 are both minimum:
by Proposition 1.15, all coins in A T -1 ∩ R 2 are isolated and all coins in A T -1 ∩ R 1 are isolated except possibly for a single pair of adjacent coins. We can see that the only way to satisfy property (i

) is if A T -1 ∩ R 1 contains a pair {c 1 , c 2 } of adjacent coins such that c 1 is adjacent to one of the coins in A T -1 \ (R 1 ∪ R 2 )
, as in Figure 16 (left). However, c 1 then violates property (ii), a contradiction.

3) Case 3: At least one of R 1 or R 2 is odd (say R 2 is odd); h is odd. Again, we just need to find one coin more than what (2), (3) and (4) give us combined, because if we do then we can conclude that:

|A| ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 + 1 ≥ m 1 + n 1 2 + m 2 + n 2 + 1 2 + h -1 2 + 1 = m 1 + n 1 + m 2 + n 2 + h + 2 2 .
Therefore, suppose for a contradiction that (2), (3) and ( 4) are all tight. For (2) and

(3), this means that A T -1 ∩ R 1 and A T -1 ∩ R 2 are both minimum: in particular, neither contains three coins such that one is adjacent to the other two. For (4), this means that

A T -1 \ (R 1 ∪ R 2
) consists exactly of one coin every two rows in the gap between R 1 and R 2 , none of which is adjacent to R 1 or R 2 since h is odd. See Figure 16 (middle). All in all, property (i) is violated, a contradiction.

4) Case 4: R 1 and R 2 are both even; h is odd.

In this case, we need to find two coins more than what (2), (3) and (4) give us combined, because if we do then we can conclude that:

|A| ≥ m 1 + n 1 2 + m 2 + n 2 2 + h 2 + 2 ≥ m 1 + n 1 2 + m 2 + n 2 2 + h -1 2 + 2 = m 1 + n 1 + m 2 + n 2 + h + 3 2 .
First of all, the same proof as in Case 3 shows that (2), (3) and (4) cannot all be tight: there needs to be some coin c in A t-1 that has (at least) two coins adjacent to it. Now suppose for a contradiction that all three inequalities become tight if we remove c i.e.: 16 (right). If c ∈ R 1 then the two coins adjacent to c in A T -1 are inside R 1 as well (indeed, as we have seen in Case 3, the fact that h is odd means that none of the

|(A T -1 \{c})∩R 1 | = m 1 +n 1 2 , |(A T -1 \{c})∩R 2 | = m 2 +n 2 2 , |(A T -1 \{c})\(R 1 ∪R 2 )| = h 2 . See Figure
h 2 coins in A T -1 \ (R 1 ∪ R 2 ) is adjacent to R 1 ). Therefore (A T -1 \ {c}) ∩ R 1 has span R 1 , and is minimum since |(A T -1 \ {c}) ∩ R 1 | = m 1 +n 1 2 . Similarly, (A T -1 \ {c}) ∩ R 2 has span R 2 and is minimum. By Proposition 1.15, all coins in (A T -1 \ {c}) ∩ R 1 and (A T -1 \ {c}) ∩ R 2 are thus isolated. Since h is odd, the h 2 coins in (A T -1 \ {c}) \ (R 1 ∪ R 2
) are also isolated. This contradicts property (ii). Proof. Let R 1 (resp. R 2 ) be the top row (resp. the bottom row) of the starting span: R 1 and R 2 are of size 3 × 1 and separated by a three row gap. Solving this puzzle would mean performing an (R 1 , R 2 )-split of the starting configuration, which is impossible by Proposition 4.5: indeed, we can easily check that it is impossible in two moves or less, and the puzzle contains

6 < 3+1+3+1+3+2 c 1 c 2 R 1 R 2 R 1 R 2 c R 1 R 2

A new sufficient condition

We now present a result that holds even when some component of span(A) contains two or more components of span(B). We would have liked conditions (i) and (ii) to be replaced by the sole condition that A has 2 extra coins relatively to B, however we are not sure how the proof would work in that case. Apart from that, the additional assumption compared to Theorem 3.1 is condition (iv), which is not about the quality of the coins involved (extra/redundant) but purely about their quantity, as was suggested by the worst-case puzzles from Corollary 4.3. Moreover, these puzzles also show that the bound from condition (iv) is almost tight: indeed, if n is odd for instance, we have min An = n and min Bn = n + 1 so that the puzzle

A n ? - → B n satisfies N = 3n-3 2 = 3
2 max(min An , min Bn ) -3, just 5 coins away from this bound.

We now proceed with the proof of Theorem 4.8. As usual, we are going to route through the canonical configurations, which means the challenge is to go from L A to L B . The proof relies on an intuitive way to do so, which consists in forming a wave of coins (by flipping 'L's) to sweep across the board while dropping coins at all positions in L B , as detailed in the proof of the following lemma. Note that this lemma is more general than we use, since the target configuration is not required to be canonical. Lemma 4.9. Let m, n ≥ 1 and let L be the canonical 'L' of size m

× n. Let k ∈ N. If a configuration C ⊆ span(L) satisfies |C| < min m+n 2 -min(m,n) 2 + (k -1), 2(k -1) , then L +k → C +k+|L|-|C| .
Proof. We proceed by induction on the half-perimeter m + n. If m = n = 1, then C = L or C = ∅ so the result is obvious. Suppose m + n ≥ 3 and assume the result holds for any half-perimeter lesser than m + n. Up to a 90 degree rotation of the board, also assume m ≤ n. We divide R := span(L) into two rectangles: a bottom half R 1 and a top half R 2 (if n is even then both halves are equal, otherwise we choose one of them arbitrarily to be bigger than the other by one row). Define

C 1 := C ∩ R 1 and C 2 := C ∩ R 2 . Up to swapping the roles of R 1 and R 2 , assume |C 1 | ≤ |C 2 |. Let n ∈ n 2 , n 2
be the number of rows of R 2 , so that R 2 is of size m × n . To reach C, we build the bottom half C 1 first, then the top half C 2 .

1 We start by building the bottom half of C. We show that L +k → C +k 0

where k := k +|L|-|C 0 | and C 0 is the configuration defined as follows: C 0 ∩R 1 = C 1 , and C 0 ∩R 2 = L 2 is the canonical 'L' of size m × n . See Figure 17. • We have 2 supporting coins that we will use to transform chains.

• We have |C 1 | building coins that we will drop at the right positions to build

C 1 . • If k > |C 1 | + 2, the remaining k -|C 1 | -2 coins will be kept in hand.
Note that the supporting coins might not remain the same throughout the moves. For example, we might drop a supporting coin, perform some moves, and then pick up a coin: in that case, the picked up coin becomes a supporting coin even if it is not "physically" the same coin that we dropped initially. We proceed in four steps.

(a) Let p be the bottom-left corner of R 2 : we want to make sure there is a coin at p.

-Case (a1): even R, odd n . There already is a coin at p.

-Case (a2): even R, even n . We drop one of our supporting coins at p.

-Case (a3): odd R. If needed, we use a leapfrog to put one of the two adjacent coins at p. Recall that a leapfrog only uses one supporting coin. (b) The board now contains an 'L' whose extremal coins are at the bottom-left corner of R 2 and the bottom-right corner of R 1 , as highlighted in Figure 18. We now use our supporting coin(s) to flip this 'L', while building C 1 in the process (see Figure 20 for the desired result). To achieve this, we take advantage of the fact that the flip sweeps over the entirety of R 1 . In the subroutines from Figures 6 and9, some positions are highlighted by a black outline: whenever one of these positions contains a coin in C 1 , we drop a building coin there at the appropriate moment during the subroutine (one example is detailed in Figure 19). Over the flip as a whole, these positions cover all of R 1 except its rightmost column, so that all of C 1 is correctly replicated at the end of this step apart from the coins in the rightmost column. Note that the 'L' that we flip is odd in case (a2), so that the lone remaining supporting coin is indeed enough to flip it. See Figure 20. (c) We now make sure there is a coin in the bottom-right corner of R 2 . If the newly flipped 'L' is odd, this is done with a leapfrog. If it is even, in particular we are not in case (a2), so we can afford to drop one of our two supporting coins at the bottom-right corner of R 2 if needed. In both cases, we still have at least one supporting coin at our disposal. We now correct the rightmost column of R 1 : we drop building coins where they are needed in the holes in-between the coins that are already on board, and then we pick up all coins in that column that are not in C 1 .

(d) At this point, R 2 either contains an 'L' or a chain that is almost an 'L' apart from the fact it has two pairs of adjacent coins (this can happen if we have dropped a supporting coin at the bottom-right corner of R 2 in step (c)). In this latter case, we use a leapfrog to retrieve the coin in excess so that R 2 contains a true 'L'. Finally, we leapfrog if needed to make this 'L' canonical, so that the full configuration on board is now exactly C 0 . These leapfrogs are always possible because we have at least one supporting coin at our disposal. See Figure 21. 2 We now build the top half of C. Since the bottom half is built already, we will not touch it, therefore we want to show that

L +k 2 → C +k +|L 2 |-|C 2 | 2
. By our induction hypothesis, since R 2 is of half-perimeter m + n < m + n (recall that m + n ≥ 3, so n ≥ 2 hence n < n), it suffices to show that |C 2 | < min m+n 2 -min(m,n ) 2 + (k -1), 2(k -1) . We now show both inequalities. Beforehand, since the total number of coins at our disposal is |L| + k and |C 1 | + |L 2 | of them are on the board at this point, note that:

k = (|L| + k) -(|C 1 | + |L 2 |) = m + n 2 + k -|C 1 | + m + n 2 . ( 5
)
• By our assumption on C, we have

|C 1 | = |C|-|C 2 | < m+n 2 -min(m,n) 2 +(k-1)-|C 2 |.
Using equality (5), we get:

k > |C 2 | + 1 + min(m, n) 2 - m + n 2 ≥ |C 2 | + 1 + min(m, n ) 2 - m + n 2 ,
where the last inequality comes from the fact that n > n . We thus get the first desired inequality:

|C 2 | < m+n 2 -min(m,n ) 2 + (k -1).
• By our assumption on C, we have k

-1 > |C| 2 ≥ |C 1 | hence k -1 -|C 1 | > 0. Moreover k -1 -|C 1 | = k -1 -|C| + |C 2 | > |C 2 | -m+n 2 + min(m,n) 2 = |C 2 | -m+n 2 + m 2 . Since all integers x > y with x > 0 satisfy x ≥ y 2 + 1, we get k -1 -|C 1 | ≥ 1 2 |C 2 | -m+n 2 + m 2 + 1. Recall that k -1 = (k -1 -|C 1 |) + m+n 2 -m+n 2
by equality (5). Therefore:

k -1 ≥ |C 2 | 2 + 1 2 m + n 2 + 1 2 m 2 - m + n 2 + 1 ≥ |C 2 | 2 + m + n 4 + m 4 - m + n+1 2 + 1 2 + 1 = |C 2 | 2 + 1 4 > |C 2 | 2 , from which |C 2 | < 2(k -1) which concludes.
Proof of Theorem 4.8. In fact, we prove a more general result where condition (iv) is replaced by the following double inequality:

N > min A + min B 2 + 1 (6) N > min B + min(m, n) 2 + 1 (7)
Let us first check that this assumption is indeed weaker. Suppose that (iv) holds, then:

• N ≥ min A + min B 2 + 2. Therefore, (6) holds. • N ≥ min B + min A 2 + 2. Since N is an integer, this yields N ≥ min B + min A 2 + 2. Moreover min A 2 = 1 2 m+n 2 = m+n 4 ≥ min(m,n) 2
, where we have used the fact that any real

number x satisfies x 2 = x 2 . Therefore, we get N ≥ min B + min(m,n) 2 + 2, so (7) holds.
Assume that conditions (i),(ii),(iii),( 6),(7) all hold. As already mentioned, we want to use Corollary 2.8 (in this case L A 0 = L A because of our assumption that A has 2 extra coins) so we need to show that

L +k A → L +k+|L A |-|L B | B
where k

:= |A| -|L A | = N -min A = N -m+n 2
. By Lemma 4.9, it suffices to show that min

B = |L B | < min m+n 2 -min(m,n) 2 + (k -1), 2(k -1) .
• By (6), we have min B < 2(Nmin A -1) = 2(k -1).

• By (7), we have min

B < N -min(m,n) 2 -1 = m+n 2 -min(m,n) 2 + (k -1).
Even though, as we have mentioned, the bound in Theorem 4.8 is tight up to an additive factor O(1) for a square span (n = m, as in A n and B n ), things might be different for a rectangular m × n span in general.

One extra coin: minimum+1 configurations

The case where A only has 1 extra coin relatively to B is even more complicated. In this section, we initiate its study with the following restrictions:

• span(A) = span(B) is a single rectangle.

• A is minimum+1, which means that A consists of a minimum configuration with same span as A plus one coin added to it. In particular, A has 1 extra coin (and not more). Note that under these restrictions, and further assuming that B has 1 redundant coin b which we know is necessary, B is also minimum+1: indeed, B \ {b} has same span as A so it is minimum by cardinality.

Even span

The case of an even span is straightforward: if A is a minimum+1 configuration with even span, then the only way to make moves from A without decreasing the span is to move the same coin over and over again.

Odd span

On the contrary, the slightly higher density of coins allows for some non-trivial movement when the span is odd. For instance, we have seen (and it was already noticed in [START_REF] Demaine | Coin-Moving Puzzles[END_REF]) that one coin in hand is enough to flip an odd 'L', so we know that the puzzle on the left of Figure 22 is solvable. On this example, the big difference compared to the even case is the presence of a pair of adjacent coins, which helps the moves and makes this "+1" situation more of a "+1.5" situation in a way. When it comes to a 90 degree rotation of an odd 'L' however, even though it is easy to do with two coins in hand, it seems impossible with just one (as noticed again in [START_REF] Demaine | Coin-Moving Puzzles[END_REF]), which we will confirm shortly so that the puzzle on the right of Figure 22 is not solvable. The challenge is to figure out where the limit is between what is achievable and what is not, and we now bring our contribution in that direction. In what follows, we fix an odd m × n rectangle R.

? ?

Figure 22. Two examples of puzzles involving minimum+1 configurations with even span. The one on the left is solvable, the one on the right is not.

Reduction to the poking game

First of all, we can make an interesting observation:

Lemma 5.2. Let A be a minimum+1 configuration, and consider a sequence of moves

A = A 0 c 1 →p 1 ----→ A 1 c 2 →p 2 ----→ A 2 → . . .

such that the span is preserved throughout and no coin is moved twice in a row. Then:

• For all t ≥ 1, A t is minimum+1.

• For all t ≥ 1, c t+1 is a neighbour of p t . In other words, the coin that we move (apart from the very first one) is always a neighbour of the most recently moved coin.

Proof. Let t ≥ 1.

• span(A t \ {p t }) = span(A t ) = span(A), therefore A t \ {p t } is minimum by cardinality, so A t is minimum+1. • Suppose for a contradiction that c t+1 is not a neighbour of p t . Since no coin in moved twice in a row, we know p t = c t+1 , so this means that p t has at least two neighbours in A t \ {c t+1 } by the 2-adjacency rule, which yields span(A t \ {c t+1 }) = span(A t \ {c t+1 , p t }). Finally, since A t+1 \ {p t+1 } = A t \ {c t+1 }, we get:

span(A t ) = span(A t+1 ) = span(A t+1 \{p t+1 }) = span(A t \{c t+1 }) = span(A t \{c t+1 , p t }) ,
therefore A t has 2 extra coins which is a contradiction.

Conceptually, it is helpful to forget about the "+1" coin, by ignoring the last moved coin at all times. This allows us to focus on the underlying minimum configuration and how it evolves during the moves. Since each coin that we move is a neighbour of the most recently moved coin, as guaranteed by Lemma 5.2, each move causes the underlying minimum configuration to see one of its coins effectively slide by one position towards another coin. An example is given in Figure 23 (the first move is ignored as it will be in the reduction to come). This inspires us to consider a new game, which is played directly on minimum configurations instead of minimum+1 configurations. Proof. If {c, c 2 } denotes the pair of adjacent coins in M 0 , then p is part of the pair of adjacent coins in M 1 and c 2 is a neighbouring coin of the free position c in M 1 which makes p P -→ c a valid poke from M 1 . Proposition 5.6. Any poke preserves the span, and the configuration obtained after a poke is still a minimum configuration with a pair of adjacent coins.

Proof. Let M be a minimum configuration with a pair {c 1 , c 2 } of adjacent coins. Let M be the configuration obtained from M after some poke c 1 P -→ p (up to swapping the roles of c 1 and c 2 ). By definition of a poke, p has a neighbouring coin c ∈ M \ {c 1 }. Obviously M contains a pair of adjacent coins, namely {p, c}. To conclude, it suffices to show that M has same span as M , because this implies that M is minimum by cardinality. In M , the position p is free but has two distinct occupied neighbours c 1 and c, therefore span(M ) = span(M ∪ {p}).

In M , the position c 1 is free but has two distinct occupied neighbours c 2 and p, therefore span(M ) = span(M ∪ {c 1 }). Since M ∪ {p} = M ∪ {c 1 }, we get span(M ) = span(M ).

We have thus introduced a poking game where, given two minimum configurations M and M whose span is the same odd rectangle and both containing a pair of adjacent coins, we ask the question whether M P -→ M . The next result is a formal proof of the reduction illustrated in Figure 23 and thus confirms that we can now focus entirely on the poking game.

Let A and B be minimum+1 configurations with span R. Suppose A = B and A → B. Then A → B if and only if there exists a move

A c 1 →p 1 ----→ A 1 and a ∈ A 1 , b ∈ B such that:
• a is a neighbour of p 1 .

• b is a redundant coin in B.

• A 1 \ {a} P -→ B \ {b}. As a consequence, the case where A and B are minimum+1 configurations whose span is the same odd rectangle reduces to the poking game, up to a factor O(N 2 ) where N := |A| = |B|.

Proof. First suppose A → B. We write

A = A 0 c 1 →p 1 ----→ A 1 c 2 →p 2 ----→ . . . c T →p T ----→ A T = B
where no coin is moved twice in a row. We know T ≥ 2 because A = B and A → B. Setting a = c 2 and b = p T , since c 2 is a neighbour of p 1 by Lemma 5.2 and p T is a redundant coin in B by the 2-adjacency rule, it suffices to show that A 1 \ {c 2 } P -→ B \ {p T }. For 2 ≤ t ≤ T , we define M t := A t \ {p t }, the intermediary configuration obtained when the moved coin from A t-1 to A t is "in the air": M t is minimum by cardinality because span(M t ) = span(A t ). Note that M 2 = A 1 \ {c 2 } and M T = B \ {p T }, so our goal is to get M 2 P -→ M T . See Figure 24, which completes Figure 23 and illustrates the full reduction to the poking game.

• First of all, we show that M 2 , . . . , M T all contain a pair of adjacent coins. Let 2 ≤ t ≤ T , we have In conclusion, we have M 2

M t = A t-1 \ {c t }. Since p t-1 ∈ A t-
c 3 P -→p 2 -----→ M 3 c 4 P -→p 3 -----→ . . . c T P -→p T -1 -------→ M T .
The proof of the converse is similar: given the first move A c 1 →p 1 ----→ A 1 and a sequence of pokes (c t P -→ p t ) 2≤t≤T from A 1 \ {a} to B \ {b} for some suitable a and b, we check that the sequence of moves A

c 1 →p 1 ----→ A 1 a →p 2 ---→ A 2 c 2 →p 3 ----→ A 3 c 3 →p 4 ----→ . . . c T -1 →p T ------→ A T c T →b
---→ B is valid. As for the last statement of this proposition, it comes from the fact there are: O(N 2 ) possibilities for the first move, at most four possibilities for a (since p 1 has at most four neighbours), and at most three possibilities for b (indeed, given a redundant coin b 0 in B, the only coins other than b 0 that might be individually redundant in B are those from the pair of adjacent coins in the minimum configuration B \ {b 0 }, because the others are isolated in B \ {b 0 } and thus have at most one neighbour in B).

A = A 0 A 1 M 2 a b M 3 M 4 M 5 A 2 A 3 A 4 A 5 = B

The poking game on minimum chains

It is natural to study the simplest minimum configurations first, namely minimum chains. We start by detailing their structure: a minimum chain with span R containing two adjacent coins goes from one corner of R to its opposite without taking any detour (i.e. in a "straight line").

Proposition 5.8. Let M = [c 1 , . . . , c N ] be a minimum chain with span R containing a pair of adjacent coins {c i 0 , c i 0 +1 } for some 1 ≤ i 0 ≤ N -1. Then:

• For all i ∈ {1, . . . , N -1}: dist(c i , c i+1 ) = 2 if i = i 0 and dist(c i , c i+1 ) = 1 if i = i 0 .
• c 1 and c N are opposite corners of R.

• If c 1 is the top-left corner of R, then for all i ∈ {1, . . . , N -1}, c i+1 is either to the right, to the bottom, or to the bottom-right of c i . The analogous assertion holds if c 1 is any other corner of R.

Proof. Following the chain from c 1 to c N , we consider the number of jumps that are made in each of the four directions. For instance, if for some i ∈ {1, . . . , N -1} the coin c i+1 is to the bottom-right of c i , then the transition from c i to c i+1 counts as one right jump plus one bottom jump, whereas if c i+1 is two positions under c i then this transition counts as two bottom jumps. The first assertion of this proposition follows directly from the definition of a chain and Proposition 1.15, and further ensures that there are 2(N -2) + 1 = m + n -2 jumps in total (indeed, recall that N = m+n+1 2 by Proposition 1.15). By Proposition 1.12, there exist t, b, l, r ∈ {1, . . . , N } such that c t (resp. c b , resp. c l , resp. c r ) is in the top row (resp. bottom row, resp. leftmost column, resp. rightmost column) of R. Without loss of generality, assume t ≤ b and l ≤ r, then at least n -1 bottom jumps are made from c t to c b and at least m -1 right jumps are made from c l to c r . Since there are m + n -2 jumps in total, we conclude that: exactly n -1 bottom jumps are made from c t to c b , exactly m -1 right jumps are made from c l to c r , and those cover all jumps made, hence the third assertion. Since no top jump or left jump is ever made, in particular there is no top jump between c 1 and c t and no left jump between c 1 and c l , therefore c 1 is the top-left corner of R. For the same reason, c N is the bottom-right corner of R, which proves the second assertion.

Recall that one coin in hand is enough to flip an odd 'L'. The following theorem, which generalizes this observation, is the central result of this section. In particular, it gives a formal proof that rotating an odd 'L' is impossible with a single coin in hand.

Theorem 5.9. If M is a minimum chain with span R containing a pair of adjacent coins, then M P -→ M if and only if M is a minimum chain between the same two coins as M .

Proof. Write M = [c 1 , . . . , c N ]. We first show the necessity, and then we give a constructive proof of the sufficiency.

• Let i 0 ∈ {1, . . . , N -1} such that the pair of adjacent coins in M is {c i 0 , c i 0 +1 }. We must show that, after a poke from M , we still obtain a chain between c 1 and c N . Without loss of generality, assume that we poke c i 0 onto some position p: we want to show that [c 1 , . . . , c i 0 -1 , p, c i 0 +1 , . . . , c N ] is a proper chain.

-We already know that, for all i ∈ {1, . . . , N -1} \ {i 0 -1, i 0 }: dist(c i , c i+1 ) ∈ {1, 2}.

-Since p is a neighbour of c i 0 other than c i 0 +1 , we have dist(p, c i 0 +1 ) = 2.

-A consequence of the third assertion in Proposition 5.8 is that, for any i ∈ {1, . . . , N -

1} \ {i 0 }: dist(c i 0 , c i ) = 2(i 0 -i) if i < i 0 and dist(c i 0 , c i ) = 2(i -i 0 ) -1 if i > i 0 .
In particular, necessarily i 0 ≥ 2 and c i 0 is poked towards c i 0 -1 , because it is the only coin at distance exactly 2 from c i 0 . This means dist(p, c i 0 -1 ) = 1.

In conclusion, the configuration obtained after the poke is

[c 1 , . . . , c i 0 -1 , p, c i 0 +1 , . . . , c N ],
which is a chain between c 1 and c N since i 0 ∈ {1, N }. Moreover, it is minimum by cardinality, because the poke preserves the span according to Proposition 5.6.

• Suppose M also forms a chain between c 1 and c N , we want to show that M P -→ M . Without loss of generality, assume that c = c 1 is the top-left corner of span(M ). Let L be the 'L' with end-points c and c that hugs the left and bottom sides of R and where the two adjacent coins are at the top-left. Since all pokes are reversible, it suffices to show that we can reach L: indeed, we would get M 1. Up to poking c 2 towards c 3 in the case where the pair of adjacent coins is {c 1 , c 2 }, we can assume that the chain [c 2 , . . . , c N ] contains two adjacent coins.

2. We can now apply the induction hypothesis on the chain [c 2 , . . . , c N ].

3. To finish, there are three possibilities depending on the direction of the jump from c 1 to c 2 . If c 2 is to the bottom of c 1 , then c 1 prolongs the 'L' we obtained by induction, so we just have to poke c 2 up towards c 1 to obtain the desired 'L'. If c 2 is to the bottom-right (resp. right) of c 1 , then we proceed as in Figure 27 (resp. Figure 29).

The poking game in general

We have just seen that, if the starting configuration M is a chain, then its end-points never move and all we can do is twist the string of coins that connects them. When playing the poking game on more general configurations, it quickly becomes apparent that certain coins are ever immobile and all we do is perform successive transformations of chains between some of them as in Theorem 5.9: -We start by transforming a certain chain inside a certain rectangle R 1 , until one of the two adjacent coins is at distance 2 from the first coin of a chain C coming out of R 1 . -We can then poke towards this coin and get a new chain, inside a new rectangle R 2 , with C prolonging one half of the previous chain. -We then transform this new chain, etc. This is illustrated in Figure 30: in this example, all the action seems to happen inside three specific rectangles (R 1 , R 2 , R 3 ), with no possibility other than transitioning from one to the other via consecutive transformations of chains. An incomplete study of the poking game in general is made in [START_REF] Galliot | A coin-moving game on graphs[END_REF], the results from which can be summarized as follows:

• First of all, Proposition 5.8 can be generalized so as to get a full understanding of the structure of minimum configurations with a pair of adjacent coins. In particular, further exploiting of the perimeter considerations glimpsed in the proof of Proposition 1.15 show that these configurations are forests in terms of the 2-connectivity (connectivity at distance 1 or 2).

• A polynomial-time algorithm returns, given a configuration M , a specific set F (M ) of coins in M (in Figure 30, these are the shaded coins). These coins are forever immobile, and all that is possible is to perform successive transformations of chains between some coins in F (M ). The set F (•) is invariant throughout the pokes.

• (If M is a chain, recall that we already have Theorem 5.9.)

• If M is a tree in terms of the 2-connectivity, then M P -→ M if and only if F (M ) = F (M ).

• If M is a forest in terms of the 2-connectivity (general case), then this does not work anymore. We conjecture that a refined algorithm provides us with an invariant that characterizes solvable puzzles, similarly to the case of trees.

Conclusion

We have made some contributions to the study of the coin-moving game initiated in [START_REF] Demaine | Coin-Moving Puzzles[END_REF].

Our focus has been on configurations with either 2 extra coins or 1 extra coin, as suggested by the authors. Indeed, we use their canonicalization technique, which effectively nullifies the extra coins beyond the first two. Stepping outside of this framework however, more extra coins might be useful, so finding necessary and sufficient conditions in the case of 3 or more extra coins remains an open problem. For the same reason, we have not explored the case of 2 extra coins and just 1 redundant coin.

In the case where there are 2 extra coins in A and 2 redundant coins in B, Theorem 4.8 gives a sufficient condition that involves the total number of coins and the perimeters of the spans of A and B. The worst-case puzzles described in Corollary 4.3 show that the bound from the theorem is tight in the case of a square span, up to an additive factor O(1). However, for a rectangular m × n span in general, it looks like discrepancy between m and n tends to make puzzles easier. For instance, and provided we have the inclusion of spans, if n = 1 then it seems easy to show that 1 extra coin and 1 redundant coin are always sufficient, and if n = 2 then we suspect that 2 extra coins and 2 redundant coins are always sufficient. In general, we think that it could be possible to improve Theorem 4.8 by using only min(m,n) 2 + O(1) additional coins. We now know of two methods to solve general puzzles with 2 extra coins in A and 2 redundant coins in B: the one from Theorem 3.1 consists in going from A to 'L's then reverse into B, while the one from Theorem 4.8 consists in going from A to an 'L' then sweep across the board and drop coins to create B. It would be good to design other solving methods that would apply to some puzzles that do not meet the conditions of either theorem, such as the the puzzle on the left of Figure 11.

As for the case of a lone extra coin, we have focused on the case where A and B are minimum+1 configurations with the same span, for which the game can be reduced to a poking game. The case of chains is completely solved. A deeper study is made in [START_REF] Galliot | A coin-moving game on graphs[END_REF]: a detailed description of the structure of minimum configurations is given, and allows for further results as well as leads towards a general solution. On the contrary, nothing is known about the structure of minimal configurations, so the general minimal+1 case remains obscure. Nevertheless, it is interesting to note that the poking game can be extended to that case (see [START_REF] Galliot | A coin-moving game on graphs[END_REF] for the details).

Finally, it is easy to check that all proofs of our sufficiency results are constructive and provide polynomial-time algorithms to find a winning sequence of moves of polynomial length. However, the complexity of the game as a whole remains unknown.

  c →p --→ B or simply A → B.

Figure 2 .

 2 Figure 2. A configuration C. From C, a possible move would be c → p 1 or c → p 2 for example. However, c cannot be moved to p 3 , because that position only has one neighbouring coin other than c.

c

  T →p T ----→ A T = B and that B \{b} consists of all isolated coins. In particular all coins in B\{b} have at most one neighbouring coin in B, so p T = b by the 2-adjacency rule. Since A T -1 \ {c T } = B \ {p T }, this means A T -1 \ {c T } consists of all isolated coins. In particular all coins in A T -1 \ {c T } have at most one neighbouring coin in A T -1 , so p T -1 = c T by the 2-adjacency rule. Continuing so, we get p

  (though unnamed). They are, to the target configuration B, the relevant analogue of what extra coins are to the starting configuration A. Definition 1.18. Let B be a configuration. A set of redundant coins in B is a subset B ⊂ B of the form B = {b 1 , . . . , b k } where, for all i ∈ {1, . . . , k}, b i has at least two neighbours in B \ {b 1 , . . . , b i-1 }. We say B has k redundant coins if it contains a set of k redundant coins.

  Proposition 1.19. Let A and B be distinct configurations. If A → B then B has one redundant coin. Proof. This is exactly Proposition 1.2. Proposition 1.20. Let B be a configuration and let B = {b 1 , . . . , b k } be a set of redundant coins in B, ordered as in the definition. Then B ↔ (B \ B ) +k . In particular, for any configuration A, we have A → B if and only if A → (B \ B ) +k . Proof. We perform B → (B \ B ) +k by picking up the coins in B , and (B \ B ) +k → B by dropping the coins in hand at b k , b k-1 , . . . , b 1 successively (which respects the 2-adjacency rule since b i has at least two neighbours in B \ {b 1 , . . . , b i-1 }).

Figure 5 .

 5 Figure 5. Left: a configuration C. Right: the associated canonical configuration L C (the top-left and bottom-left 'L's are even, the top-right and bottom-right 'L's are odd).

Figure 6 .Figure 7 .

 67 Figure 6. Subroutines used to flip an even 'L'. The bottom subroutine is only used if both sides are even.

Figure 8 .

 8 Figure 8. A leapfrog. Intermediary states cover all possible locations of the pair of adjacent coins.

Figure 9 .Figure 10 .

 910 Figure 9. Subroutines used to flip an odd 'L'.

Figure 12 .

 12 Figure 12. Trimming a 7 × 4 'L' to its right, making it 4 × 4 (top) or 5 × 4 (bottom). The numbers above the arrows refer to the three steps.

Theorem 3. 3 .

 3 Let A and B be configurations such that |A| = |B|, and suppose that: (i) A has 2 extra coins relatively to B, and more precisely: there exist a 1 = a 2 in A such that span(A \ {a 1 , a 2 }) ⊇ span(B) and each component of span(A \ {a 1 , a 2 }) contains at most one component of span(B). (ii) B has 2 redundant coins. Then A → B. Proof. Let A 0 := A \ {a 1 , a 2 }. By Corollary 2.8, it suffices to show that L +|A|-|L A 0 | A 0 → L +|B|-|L B | B . Since each component of span(A 0 ) contains at most one component of span(B), we can use Lemma 3.2 to shrink each 'L' in L A 0 to the size of the corresponding 'L' in L B 0 . This is always possible, because we start off with |A| -|L A 0 | ≥ |A| -|A 0 | = 2 coins in hand and this number cannot decrease each time we shrink an 'L'.

Figure 13 .

 13 Figure13. Two puzzles satisfying condition (i) but not (ii). The left puzzle is solvable in 4 moves, while the right puzzle is unsolvable.

Figure 15 .

 15 Figure 15. Definition of the puzzle A n ? -→ B n (here n = 9). The shaded coins represent the extra/redundant coins.

Corollary 4. 6 .

 6 The puzzle on the right of Figure11is unsolvable.

Figure 16 .

 16 Figure 16. The configuration A T -1 : a contradiction in Case 2 (left), Case 3 (middle) and Case 4 (right).

Notation 4. 7 .

 7 Let C be a configuration. We denote by min C the cardinality of minimum configurations with same span as C. Note that, if this span is an m × n rectangle, then min C = m+n 2 by Proposition 1.15. Theorem 4.8. Let A and B be configurations such that |A| = |B| =: N and: (i) span(A) ⊇ B is a single m × n rectangle. (ii) A has 2 extra coins. (iii) B has 2 redundant coins. (iv) N ≥ 3 2 max(min A , min B ) + 2. Then A → B.

Figure 17 .

 17 Figure 17. An example of a configuration C (left) with its associated configuration C 0 (right).

Figure 18 .

 18 Figure18. The board after step (a). From left to right: case (a1), case (a2), case (a3).

Figure 19 .

 19 Figure19. How to drop a building coin at any desired position (here we drop four of them, but we can drop less). The building coins are shaded.

Figure 20 .

 20 Figure 20. Left: a configuration C (the same example as in Figure 17). Middle: the board after step (a). Right: the board after step (b).

Figure 21 .

 21 Figure 21. Step (d) performed as follow-up to Figure 20.

Proposition 5. 1 .

 1 Let A = B be minimum+1 configurations such that span(A) = span(B) is an even rectangle. Then A → B if and only if A → B. Proof. Write B = M ∪ {b} where M is a minimum configuration with same span as B. Since this span is an even rectangle, we know M has all isolated coins by Proposition 1.15, therefore A → B if and only if A → B by Proposition 1.3.

Figure 23 .

 23 Figure 23. Top: a sequence of moves (the last moved coin is shaded). Bottom: evolution of the underlying minimum configuration obtained by deleting the last moved coin.

Figure 24 .

 24 Figure 24. Top: a sequence of moves. Bottom: the corresponding reduction to the poking game, obtained by making the first move, deleting a, making a sequence of pokes, and then adding b.

P

  ← → L P ← → M . We prove this by induction on |M |. The case |M | = 2 is trivial. Now assume |M | ≥ 3 and suppose the result holds for chains of cardinality lesser than |M |.

Figure 25 .

 25 Figure 25. The poking version of the leapfrog.

Figure 26 .Figure 27 .

 2627 Figure 26. Subroutines used when c 2 is to the bottom-right of c 1 .

Figure 28 .Figure 29 .

 2829 Figure 28. Subroutines used when c 2 is to the right of c 1 .

Figure 30 .

 30 Figure 30. Playing the poking game. The outlined rectangle shows the chain that is currently being transformed. The shaded coins seem unmovable.

Definition 1.16. Let

  A be a configuration and k ∈ N. • A set of extra coins in A is a subset A ⊂ A such that span(A \ A ) = span(A). We say A has k extra coins if it contains a set of k extra coins. For example, A has one extra coin if and only if A is not minimal. • Let B be a configuration. A set of extra coins in A relatively to B is a subset A ⊂ A such that span(A \ A ) ⊇ span(B). We say A has k extra coins relatively to B if it contains a set of k extra coins relatively to B. If A and B have same span, then this definition coincides with the previous one.

			b 1
		a 1	?
		a 2
			b 2
	Figure 4. An example of a puzzle with two extra coins a 1 , a 2 (Definition
	1.16) and two redundant coins b 1 , b 2 (Definition 1.18).
	For example, in the puzzle A	? -→ B from Figure 4, {a 1 , a 2 } is a set of extra coins in A (in
	particular, it is also a set of extra coins in A relatively to B).
	Proposition 1.17. Let A and B be distinct configurations. If A → B then A has one extra
	coin relatively to B.

  1 , we know p t-1 ∈ M t : indeed, no coin is moved twice in a row hence p t-1 = c t . Moreover p t-1 has two neighbours in A t-1 by the 2-adjacency rule, so it has one neighbour in M t . We have(M t \ {c t+1 }) ∪ {p t } = A t \ {c t+1 } = A t+1 \ {p t+1 } = M t+1 sothe poke c t+1 P -→ p t (if valid) does transform M t into M t+1 . -We know c t+1 ∈ A t , moreover c t+1 = p t since no coin is moved twice in a row, so c t+1 ∈ M t . -Obviously p t ∈ M t by definition of M t . -By Lemma 5.2, c t+1 is a neighbour of p t . -It only remains to check that c t+1 is part of the pair of adjacent coins in M t . But if it were not the case, then the (illegal) poke would create a second pair of adjacent coins i.e. M t+1 would contradict Proposition 1.15.

• Let 2 ≤ t ≤ T -1, we check that c t+1 P -→ p t is a valid poke from M t to M t+1 .

-

coins.


Dr Qi Wei

Dr Ruihong H Duan

Dr Qi Zhang

Linghai Xie

Ruidong Xia

Yuanping Yi
email: ypyi@iccas.ac.cn

Jérémie Léonard

Stefan Haacke

Dr Juan Cabanillas-Gonzalez

Yan Qian
email: iamyqian@njupt.edu.cn

Wei Huang

Prof W Huang

Prof Y Qian

Prof. R D Xia

Prof L H Xie

Prof. Y P Yi

Prof J Léonard

Prof. S Haacke

Origin of Intramolecular Low-Threshold Amplified Spontaneous Emission

Keywords: organic lasers, organic semiconductors, amplified spontaneous emission

Amorphous thin films from solution-processable semiconductors are key materials for low-cost and large area optoelectronics. Design rules towards novel amorphous compounds with outstanding light emission and light amplification properties require understanding of the intimate relation between chemical and electronic structure. Here, we delicately design a series of compounds with tunable electronic transition characters of the lowest excited state, from local excited (LE), hybrid local charge-transfer (HLCT) to chargetransfer (CT) character. By deploying a combination of computational calculations and femtosecond-transient absorption experiments (TAS), we show that pure LE states strongly coupled to high wavenumber vibrational modes favors to form a few dominant discrete vibrational levels and are essential for optical gain, whereas HLCT or CT states preferably coupled to low frequency vibrational modes and forms a large number of consecutive vibrational levels which leads to broad excited-state absorption overwhelming stimulated emission. Our results provide guidelines for the rational design of efficient organic laser materials.

Introduction

Solid-state organic film lasers are promising broadly tunable coherent sources, which possess the benefits of low-cost processing, large compatibility with various substrates, and easy tuning of optoelectronic properties by molecular tailoring. [1][2][3][4][5][6][7][8] In the last decades, the quest for electrically-pumped organic lasers has triggered a vast effort towards both the synthesis of organic semiconductors merging outstanding photonic and charge transport properties [9][10][11][12][13][14][15] and towards the development of high quality factor laser cavities. [16,17] From the materials design point of view, an optical gain medium must support excellent optical waveguiding [18,19] as well as exhibit stimulated emission (SE) [20][21][22] . Whilst the former element relies on considerations of refractive index and homogeneity of the film (thickness value, thickness uniformity or absence of scattering inhomogeneities), SE depends on the photophysics of the film, being in particular sensitive to the nature of the lowest excited state responsible for emission and its associated features like radiative and non-radiative decay rates, concurrence of excited state absorption and SE in the same spectral regions or intramolecular electronphonon coupling. However, realization of amorphous thin-film organic lasers which generally exhibit a single amplified stimulated emission (ASE) is hindered by the lack of understanding the origin at the intramolecular level. General explanation of ASE is population inversion between two higher-energy levels, but it is too universal and still cannot tell which compounds easily feature population inversion and thus realize low-threshold ASE.

In this work we provide a direct visualization on how systematic chemical modification impacts on the SE properties of a new family of conjugated molecules, all sharing a common core consisting of a carbazole-substituted diarylfluorene. This bulky outof-plane central unit provides large steric hindrance, inhibiting severe aggregation and enabling prominent solid-state luminescence characteristics. [11,15,23] Five different compounds are synthesized by connecting the common central diarylfluorene core with trifluoromethylphenyl-, fluorophenyl-, phenyl-, biphenyl-and fluorene-end groups which delicately confers their lowest excited states with a different character, from charge transfer (CT) by localization of the electron (hole) in the fluorene (carbazole) unit, to hybrid local charge-transfer (HLCT) or local excited (LE) characters. An in-depth investigation on the structure-property relationship is carried out in order to correlate the SE property with the nature of the lowest excited-states. We demonstrate that lowest CT states detrimental for SE can be de-stabilized in favor of LE states upon removing the electron withdrawing substituents and extending the conjugation around the fluorene core, giving rise to outstanding optical gain properties. This work has interesting implications for the rational design of organic laser materials.

Results and discussion

Five carbazole substituted arylfluorenes, namely SFFCz, SCF3FCz, SPhFCz, SBPhFCz and SPFFCz, were synthesized by room-temperature BF3•Et2O-mediated Friedel-Crafts reaction of various tertiary alcohols of 2,7-aryl-substituted 9-phenyl-9H-fluoren-9-ol with 9-octyl-9Hcarbazole (see the chemical structures in Figure 1a and the synthesis routes in Scheme S1 in Supporting Information). The molecular structures and purities were confirmed by 1 H and 13 C NMR spectroscopy, MALDI-TOF MS and elemental analysis (See Supporting Information).

The N-substituted octyl groups in the carbazole units enable large solubility and thus solution processability for film preparation. The substitution of the phenyl ring and carbazole via sp 3 -C of the 2,7-aryl-substituted fluorenes provide rotational flexibility of the former, bringing large steric hindrance, preventing otherwise severe emission quenching in condensed films and ensuring large thermal stabilities. Indeed, the fluorescence quantum efficiency (φf) values of SFFCz, SCF3FCz, SPhFCz, SBPhFCz and SPFFCz films are high: 52%, 50%, 39%, 47% and 66%, respectively. The corresponding degradation temperatures were 436, 377, 451, 459, and 433°C, respectively, while the glass transition temperatures were 87, 134, 88, 124 and 94°C, respectively (see Figure S1 and S2 in Supporting Information). These moderately high glass transition temperatures suggest good film forming abilities of the five compounds.

As the carbazole units display a non-conjugated connection to sp 3 -C of the 9phenylfluorenes, the conjugation length is thus mainly determined by the parent chain of 2,7aryl-substituted 9-phenylfluorenes, hence depending on the different aryl substituents.

Consistently, SFFCz, SCF3FCz and SPhFCz (all with maximum absorption wavelength (λabs) around 303 nm) exhibit almost identical absorption spectra, while SBPhFCz (with λabs of 343 nm) and SPFFCz (with λabs of 355 nm) show absorption red-shifts due to their larger conjugation lengths (Figure 1b and Figure S3 in Supporting Information).

Despite the identical absorption spectra of SFFCz, SCF3FCz and SPhFCz, their photoluminescence (PL) exhibit significant differences; SPhFCz possesses a vibronically resolved PL spectrum with maximum at 388 nm whereas SFFCz and SCF3FCz exhibit featureless PL with maxima at 417 and 413 nm respectively. SBPhFCz and SPFFCz with enhanced conjugation lengths show sharper, vibronically resolved PL and bathochromic shifts with maxima at 423 and 430 nm respectively. The PL dynamics in SBPhFCz and SPFFCz films follow mono-exponential decays with PL lifetimes of 760 ps (kr = 6.2 × 10 8 s -1 ) and 740 ps (kr = 8.9 × 10 8 s -1 ) respectively (see Figure S4, Table S1). Bi-exponential PL decays were instead found on SFFCz and SCF3FCz with amplitude-averaged lifetimes of 12.28 ns (kr = 4.3 × 10 7 s -1 ) and 13.64 ns (kr = 3.7 × 10 7 s -1 ) respectively. Similarly, SPhFCz exhibits biexponential PL decay with 2.06 ns average lifetime (kr = 1.89 × 10 8 s -1 ). A summary of the PL emission peaks together with their φf values, average PL lifetimes (τav) and radiative (nonradiative) decay rates kr (knr) is shown in Table 1.

Optical gain from thin films was assessed with a widely described method consisting of pumping them with a pulsed narrow stripe of light and detecting the waveguided luminescence at the film edge. [11,14] Among the five compounds, only SBPhFCz and SPFFCz exhibited amplified spontaneous emission (ASE), centered on the sharp 0-1 fluorescence peak at 419 and 426 nm, respectively. The measured ASE thresholds of SBPhFCz and SPFFCz were 2.95 and 1.59 μJ/cm 2 , respectively.

We first carried out time-dependent density functional theory (TDDFT) calculations in order to elucidate the excited-state electronic-structure properties of these related molecular structures (see the computational details in the Supporting Information). As seen in Figure 2 and Table S2, the lowest singlet exited state (S1) of both SFFCz and SCF3FCz is a chargetransfer (CT) state with the hole located on the electron-donating carbazole unit while the electron being localized on the fluoro-biphenyl or trifluoromethyl-biphenyl fluorene units.

Transitions from S0 to S1 are weakly allowed as confirmed by the low oscillator strength (f) values associated to the CT states. In contrast with S1, the second and third singlet excited states (S2 and S3) have an increased hole localization on the biphenyl fluorene unit, giving rise to a hybrid local charge transfer (HLCT) character and relatively strong oscillator strengths in both of them. Regarding SPhFCz, the S1 state has HLCT character whereas the S2 and S3

states have CT character and local excitation (LE) character on the carbazole unit, respectively. Both S2 and S3 share low f values due to the associated transitions being symmetry forbidden. The S1 state of SPhFCz lies between the S2 and S3 levels of SFFCz or SCF3FCz, agreeing with the similar absorption spectra of the three compounds (Figure 1b).

On the other hand, because of the elongated conjugation, the S1 states of SBPhFCz and SPFFCz become LE states on the bis(biphenyl) fluorene or terfluorene backbones, and exhibit much enhanced oscillator strengths as well as decreased excitation energies; however, the S2 and S3 states are CT states. Notably, the predicted S1 characters of the five compounds are consistent with the presence/absence of PL spectral shifts in solvents with different polarity. Indeed, because of the CT character, SFFCz and SCF3FCz show large bathochromic shifts in the PL spectra upon replacing nonpolar n-hexane solvent by high polar acetonitrile (see Figure S5 in Supporting Information). Contrarily, the PL spectra of SBPhFCz and SPFFCz exhibit almost no shift upon changing the solvent polarity due to the LE character of S1. The HLCT character of S1 in SPhFCz is reflected in small shifts in solvents with no or weak polarity but large red-shifts in highly polar solvents.

The PL spectral shapes are also in line with the predicted character of S1 in the different compounds. SBPhFCz and SPFFCz with LE character show clear vibronicallyresolved PL spectra whereas the other three compounds with CT or HLCT characters show broader featureless PL. To further reveal the influence of the transition characters on the emission spectra, we have theoretically calculated the fluorescence spectra and analyzed the role of molecular vibrations for SFFCz and SBPhFCz, as representatives of CT and LE transitions, respectively. The calculated fluorescence spectra (Figure 3a) agree well with the experimental ones in n-hexane (Figure S3); SFFCz shows a single broad peak whereas SBPhFCz exhibits three distinguishable vibronic peaks with the 0-0 transition slightly stronger than the 0-1 transition. Note that because of self-absorption effects in the solid phase, the 0-0 transition is much weaker than the 0-1 transition, as observed in the SBPhFCz film (Figure 1b). Based on the essential active vibrational modes (with Huang-Rhys factors S > 0.1, see Figure 3b), the vibrational transition probabilities (so-called Franck-Condon factors, see Figure 3a) are calculated to be approximately a continuous curve for SFFCz but more discrete for SBPhFCz. The enhanced vibronic structure of the SBPhFCz PL is attributed to a decreased vibronic coupling of the low-frequency vibrational modes and a stronger vibronic coupling of the high-frequency backbone stretching modes (Figure 3b-c). The stronger vibronic couplings of the high-frequency vibrations increase the intensity of the 0-1 sub-band whereas the stronger couplings of the low-frequency vibrations broaden the sub-bands and lead to less resolved PL spectra (Figure 3a, S6, and S7). As seen in Figure 3c, the strongest vibronic couplings in SFFCz are ascribed to low frequency torsional modes; for instance, S = 6.2 at 14.5 cm -1 and 19.0 at 20.8 cm -1 . The vibronic coupling is quadratically proportional to the normal mode displacement (see eq S3). [24,25] In SFFCz, the torsional vibrations include all the moieties in the molecules and the inter-fragment displacements are particularly obvious (Figure 3c and S8a), due to the significant change in electronic density upon CT transition. This significant inter-fragment geometry change causes SFFCz to have large vibronic coupling in the very-low-frequency region, detrimental for the formation of the well-resolved vibronic peaks in the PL spectrum. Conversely, benefiting from the LE character of S1, SBPhCz torsional vibrations are confined in the bis(biphenyl) fluorene fragment and there is no inter-fragment geometry change (Figure 3c andS8b). In the low-frequency region, the largest vibronic couplings correspond to higher frequency modes for SBPhCz, e.g. S = 1.2 at 26.4 cm -1 and S = 4.8 at 89.1 cm -1 . This is advantageous to form discrete energy levels for efficient population inversion required in ASE. As a result, SBPhCz exhibits a narrower and fine-structured PL spectrum while SFFCz exhibit a broad spectral shape. These different PL spectral shapes have also implications in the optical gain properties of the five compounds since larger optical gain coefficients are generally expected when the PL is concentrated in a narrower spectral range. Thus, the narrower and well-resolved PL of SBPhFCz and SPFFCz affords a priori better characteristics for efficient ASE and lasing. nm range where SE is expected to be located. This is in line with the predicted very weak oscillator strength of the CT-S0 transition (Fig 2a). Lack of SE is also evident at longer time delays whereas the spectra experience a slight blue shift towards 541 nm ascribed to vibrational cooling. The A spectra of SPhFCz at 0.6 ps delay (Figure 4c) depicts strong ESA extending well beyond 600 nm with a shoulder around 550 nm. As time elapses beyond 10 ps, the tail vanishes leaving a prominent absorption band underneath with maximum at 549 nm and similar spectral characteristics as the one observed in SFFCz and SCF3FCz. The presence of SE buried underneath the dominant ESA is plausible from the inverted PL-like shape of the valley between 370 and 450 nm absorption region. It appears that ESA has a higher oscillator strength than SE, explaining the positive ΔA in this spectral region. Absence of SE is also found in the A spectra of the three compounds in chloroform solution (Figure S9), confirming that the cause of SE quenching is merely intra-molecular. Clearly, these films show photo-induced loss rather than optical gain. Contrarily, the ΔA spectra of SBPhFCz and SPFFCz (Figure 4d-e) reveal a very different photophysical scenario. Herein, the LE character of S1 is manifested through the observation of a negative A band in the 400-440 nm spectral range (superposed with their respective PL spectra) due to SE, in line with the strong oscillator strength predicted for the S0-LE transition. At 0.6 ps delay the SE band is accompanied by a falling tail in the short wavelength range (350-400 nm) assigned to ground state bleach and by a broad ESA with a maximum beyond 650 nm in the long wavelength range. The ESA becomes gradually broader and more pronounced on the central part of the visible spectrum. As a result, the A spectra above 34 ps are composed of ground state bleach up to 375 nm followed by broad absorption centered around 525 nm and absence of SE.

Importantly, this new contribution is apparently absent in the ΔA spectra in solution (Figure S9), as revealed by the presence of SE in timescales up to 1 ns. We ascribe this new built-in contribution to inter-chain polaron-pairs formed in the condensed phase, which are often reported in oligo-and polyfluorene films and characterized by similar broad photoinduced absorption in the green-yellow spectral range. [26][27][28][29][30][31][32][33][34][35] In summary, SFFCz, SCF3FCz and SPhFCz do not display stimulated emission (SE) in line with the very low oscillator strength associated to their lower S1 excited states; the 400 -500 nm spectral range of the ΔA spectra is in all cases dominated by ESA, explaining their inability to generate optical gain, and absence of ASE. This is mainly ascribed to the detrimental presence of CT and HLCT states showing predominant ESA over SE. [36,37] Contrarily, spatial elongation of the aryl-substituted fluorene-phenyl arms in SBPhFCz and SPFFCz lifts up the CT states favoring the formation of lowest LE excited states. These LE states have a much higher oscillator strength (Figure 2) and are strongly and preferentially coupled to high frequency modes located in the bis(biphenyl) fluorene fragment, leading to narrower vibronically resolved lineshape distributions. Altogether, this largely favors SE over ESA.

Conclusion

In conclusion, a series of carbazole substituted arylfluorenes with different CT and LE excited-state contributions tuned by varying their conjugation lengths and substituents have

Experimental Section

The synthesis and characterization of the five materials are described in SI. UV-vis absorption and PL spectra were recorded using a Shimadzu UV-3150 and RF-5300PC spectrometer, respectively. Lifetimes were measured using an Edinburgh FLSP-920 lifetime spectrometer with a 375 nm laser (typical pulse width: 55 ps; pulse repetition frequencies: 20 MHz). For ASE measurements, the samples were optically pumped at 375 nm with a Q-switched, neodymium ion doped yttrium aluminum garnet [Nd 3+ :YAG] laser (3 ns pulses at a repetition rate of 10 Hz) with a cylindrical lens to form a 4 mm × 550 μm stripe-shaped excitation area on the sample. The threshold is defined as the pump intensity at which the FWHM linewidth of the emission spectrum halves.

In the TAS setup, an amplified 5kHz Ti: sapphire laser generates 30 fs 0.5 mJ pulses to pump a commercial optical parametric amplifier (TOPAS: Light Conversion), from which 50-60 fs pulses are derived to excite the samples at 320 nm. A white light continuum is generated in a 2 mm thick CaF2 crystal, mounted on an oscillating loudspeaker to reduce photo-damage. The beam is split in two: the probe that is sent through the sample, and a reference beam is used for measuring and compensating the white-light intensity fluctuations.

The polarization of the probe beam is set at magic angle (54.7°) with respect to the pump. The synthesis and characterization of SPFFCz has been described in detail in our previously reported publication. [1] 2. Thermal Stabilities S2). For simplification, all the octyl groups were replaced by methyl for the five studied molecules in the calculations. All the DFT/TDDFT calculations were carried out by Gaussian 09 program. [2] Natural transition orbitals (NTOs) were obtained for the excitation from the ground state to the lowest three excited states to examine their transition nature. Based on the optimized S0 and S1 geometries and vibration modes, the vibronic couplings, namely Huang-Rhys factors were calculated and the fluorescence spectra were obtained by the thermal vibration correlation function (TVCF) method, as implemented in the MOMAP program. [3] Table S2. Vertical excitation energies of S1, S2, and S3 for the studied compounds calculated by TDDFT. For the strong absorbing states, the absorption wavelength are listd in brackets. respectively. In strong coupling case (S>1), the most probable transition is the 0-Round(S) transition.

Further

  insights on the optical gain properties require monitoring SE and excited state absorption (ESA) in the time domain with femtosecond transient absorption spectroscopy.

Figure 4

 4 Figure 4 depicts the differential absorption (ΔA) spectra of the five compounds in film at time

  been synthesized and studied. Due to the different energy level ordering of their LE (or HLCT) and CT excited states, only SBPhFCz and SPFFCz bearing longer conjugation length and lowest-lying LE state exhibit low-threshold ASE. Strong coupling of LE states with few high frequency modes leads to the presence of strong vibronically resolved SE overwhelming the long tail of ESA. Contrarily, short conjugated SCF3FCz and SFFCz (SPhFCz) depict lowest CT (HLCT) states with negligible SE contribution overwhelmed by ESA. This work highlights the importance of pure LE states stabilized by an extended conjugation and absence of push-pull charge effects on the fluorine moieties, gives enlightenment for future rational design of the organic laser materials.

  Time-resolved spectra I() are acquired as a function of pump-probe delay, by a combination of 25 cm focal length spectrometer (resolution 2 nm) and a Peltier-cooled CCD with 220 Hz acquisition rate. A second chopper blocks the pump beam at 110 Hz and a home-made software computes the differential spectra ∆𝐴 = -𝑙𝑜𝑔 10 ( 𝐼 𝑝𝑢𝑚𝑝-𝑜𝑛 𝐼 𝑝𝑢𝑚𝑝-𝑜𝑓𝑓). A reference sample is measured, and the data are processed to (i) remove the background at negative delay times, (ii) the solvent Raman signal and the coherent interactions of the pump and probe in the cell, (iii) to correct for the group velocity dispersion of the probe beam, characterized in the solvent-only data set.

Figure 1 .

 1 Figure 1. (a) Chemical structures; (b) Absorption, fluorescence, and ASE spectra of the carbazole substituted diarylfluorene compounds in films.

Figure 2 .

 2 Figure 2. (a) Excitation energies, oscillator strengths (denoted below the energy levels), and main transition characters; (b) Natural transition orbitals for the lowest three singlet excited states (S1, S2, and S3).

Figure 3 .

 3 Figure 3. (a) Calculated fluorescence spectra and related multi-mode Franck-Condon factors; (b) Vibronic couplings (Huang-Rhys factors) for the S1→S0 transition; (c) Illustration of the low-frequency (< 200 cm -1 ) and high-frequency (> 200 cm -1 ) vibration modes with the largest Huang-Rhys factors (S) for the S1→S0 transition in SFFCz and SBPhFCz.

Figure 4 .

 4 Figure 4. ΔA spectra at different time delays of (a) SFFCz, (b) SCF3FCz, (c) SPhFCz, (d) SBPhFCz, (e) SPFFCz in films. Note that only SPFFCz and SBPhFCz exhibit SE (displayed as negative ΔA in the 400-475 nm spectral region).

2. 1 Figure S2 . 3 .Figure S3 .Figure S4 .

 1S23S3S4 Figure S1. TG curves of of the carbazole substituted arylfluorenes.

Figure S6 .

 S6 Figure S6. The single-mode Franck-Condon factor of the 0-ν transition with the most representative vibrational mode (mode with the largest S) in low-and high-frequency region for SFFCz and SBPhFCz, respectively.

Figure S7 .

 S7 Figure S7. The double-mode Franck-Condon factor for SFFCz and SBPhFCz, the most representative vibrational mode (with the largest S) in low-and high-frequency region are selected and the '0-ν' written in the figure is for the high-frequency mode.

Figure S8 . 7 .

 S87 Figure S8. Comparison of the optimized structures between the S0 (in gray) and S1 (in purple) states for (a) SFFCz and (b) SBPhFCz. 7. Transient absorption spectra in solutions

Table 1 .

 1 The photophysical parameters of filmsThe intramolecular low-threshold ASE is highly correlated to the character of the lowest excited states. The pure local excited state favors ASE with discrete vibrational levels for efficient population inversion. The charge transfer state exhibit no ASE because its significant inter-fragment geometry change causes large vibronic coupling in the low-frequency region, difficult to form well-resolved vibrational energy levels. Qi Wei ‡ , Ruihong Duan ‡ , Qi Zhang, Linghai Xie, Ruidong Xia, Yuanping Yi*, Jérémie Léonard, Stefan Haacke, Juan Cabanillas-Gonzalez*, Yan Qian*, and Wei Huang*

	Compound	τav [ns] a)	φf	kr [10 9 ns]	knr [10 9 ns]
	SFFCz	12.28	52%	0.043	0.038
	SCF3FCz	13.64	50%	0.037	0.037
	SPhFCz	2.06	39%	0.189	0.296
	SBPhFCz	0.76	47%	0.618	0.697
	SPFFCz	0.74	66%	0.891	0.459
	a) the average lifetime of the fluorescence decay

Origin of Intramolecular Low-Threshold Amplified Spontaneous Emission

	Synthesis	of	3-(2,7-di([1,1'-biphenyl]-4-yl)-9-phenyl-9H-fluoren-9-yl)-9-octyl-9H-
	carbazole (SBPhFCz)
	BF3·Et2O (1.3 ml, 9.16 mmol) was added to anhydrous CH2Cl2 (100ml) solution of DRFOH
	(2.48 g, 2.4 mmol) and 9-octyl-9H-carbazole (0.62 g, 2.2 mmol), and the batch was stirred
	over a period of 5 h at room temperature. The resulting mixture was washed by water and
	extracted with CH2Cl2. The residue then subjected to silica-gel column chromatography to
	afford 2.08 g white solid in 73% yield. 1 H NMR (400 MHz, CDCl3) δ 8.08 (s, 1H), 7.98-7.94
	(d, J = 7.8 Hz, 1H), 7.94-7.90 (d, J = 7.9 Hz, 2H), 7.80 (s, 2H), 7.74-7.65 (m, 6H), 7.55 (s,
	1H), 7.53 (s, 3H),7.50-7.27 (m, 15H), 7.16-7.11 (t, J = 7.1 Hz, 1H), 4.28-4.20 (t, J = 7.2 Hz,
	2H), 2.03-1.90 (t, J = 7.2 Hz, 8H), 1.88 -1.78 (m, 2H), 1.42-0.96 (m, 50H), 0.87-0.74 (m,
	15H), 0.73-0.55 (m, 8H). 13 C NMR (400 MHz, CDCl3) δ 152.99, 151.40, 151.03, 146.89,
	141.26, 140.82, 140.76, 140.37, 140.19, 139.40, 138.97, 136.18, 128.44, 128.40, 126.98,
	126.80, 126.76, 126.69, 126.46, 126.10, 125.62, 125.03, 122.90, 122.77, 122.70, 121.37,
	120.46, 120.43, 119.85, 119.80, 119.71, 118.70, 108.64, 108.60, 65.89, 55.15, 43.22, 40.37,
	31.82, 31.78, 30.07, 30.05, 29.75, 29.38, 29.25, 29.23, 29.22, 29.19, 29.07, 27.36, 23.81,
	22.61, 14.10. MALDI-TOF m/z: 1295.58 [M] + . Anal. Calcd. for C97H117N (1295.92): C,
	89.83; H, 9.09; N, 1.08%; found: C, 89.75; H, 9.30; N, 1.12%.
	Synthesis of 9-octyl-3-(9,9,9'',9''-tetraoctyl-9'-phenyl-9H,9'H,9''H-[2,2':7',2''-terfluoren]
	-9'-yl)-9H-carbazole (SPFFCz)

Table S1 .

 S1 PL lifetime parameters in the films The molecular geometries were optimized by density functional theory (DFT) for the ground state (S0) and by time-dependent DFT (TDDFT) for the lowest singlet excited state (S1) at the MPW1B95/6-31G(d,p) level, which can well reproduce the experimental maximum absorption wavelengths (see Table

	5. Solvent-dependent Fluorescence Spectra 6. Theoretical calculations
	10 2 10 3 350 0.0 0.2 0.4 0.6 0.8 1.0 Computational details. 400 450 500 Wavelength (nm) 550 Counts Normalized PL Intensity	600 SFFCz n-Hexane 650 DCM THF IPA EtOH CH 3 CN	Normalized PL Intensity	0.0 0.2 0.4 0.6 0.8 1.0	350	400	450 Wavelength (nm) 500 550 SFFCz 600 SCF 3 FCz 650 SPhFCz SBPhFCz SPFFCz SCF 3 FCz n-Hexane THF IPA EtOH CH 3 CN DCM
	Normalized PL Intensity	1 10 1.0 0.2 0.4 0.6 0.8	0				50 n-Hexane DCM THF IPA CH 3 CN SPhFCz EtOH	1.0 Decay Time (ns) 0.2 0.4 0.6 Normalized PL 0.8 Intensity	100	EtOH SBPhFCz CH 3 CN n-Hexane DCM THF IPA	150
		0.0									0.0
		350	400	450	500	550	600	650			350	400	450	500	550	600	650
				Wavelength (nm)								Wavelength (nm)
		1.0
							n-Hexane
	PL Intensity	0.6 0.8		τ1 [ns]			DCM THF IPA CH 3 CN EtOH			τ2 [ns]				<τav> [ns] a)	χ 2
	SFFCz SCF3FCz 0.2 0.4 Normalized		5.48 (30.88%) 6.24 (34.56%) SPFFCz			15.33 (69.12%) 17.55 (65.44%)		12.28 13.64	1.073 0.929
	SPhFCz 0.0		1.17 (62.13%)				3.52 (37.87%)		2.06	1.129
		350	400	450	500	550	600	650
	SBPhFCz		0.76 Wavelength (nm)				-					0.76	1.148
	SPFFCz a) Figure S5. Solvent-dependent fluorescence spectra of the carbazole substituted arylfluorenes 0.74 -0.74 1.214 the average lifetime (1×10 -5 mol/L).

Acknowledgements

Q. Wei and R. H. Duan contributed equally to this work. We thank the Ministry of Science and Technology of China (Grant No. 2018YFA0703200), the National Natural Science Foundation of China (Grant Nos. 21573111), the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD, YX03001), Jiangsu National Synergetic Innovation Center for Advanced Materials (SICAM), Synergetic Innovation Center for Organic Electronics and Information Displays, Six Talents Peak Project of Jiangsu Province (XCL-076), Qing Lan Project of Jiangsu Province for their financial support. J.C-G acknowledges support from the Regional Government of Madrid through NMAT2D-CM project (S2018/NMT-4511) and RTI2018-097508-B-I00 (AMAPOLA). IMDEA Nanociencia acknowledges support from the "Severo Ochoa" Programme for Centers of Excellence in R&D (MINECO, Grant SEV-2016-0686).

((will be filled in by the editorial staff)) Revised: ((will be filled in by the editorial staff))

Supporting Information

Supporting Information is available from the Wiley Online Library or from the author.

Supporting Information

Origin of Intramolecular Low-Threshold Amplified Spontaneous Emission

Qi Wei ‡ ) solution of DRFOH (1.0 g, 2.1 mmol) and 9-octyl-9H-carbazole (0.56 g, 2.0 mmol), and the batch was stirred over a period of 5 h at room temperature. The resulting mixture was washed by water and extracted with CH2Cl2. The residue then subjected to silica-gel column chromatography to afford 0.44 g white solid of SFFCz in 30% yield. 1 Based on the Fermi golden rule and Condon's approximation, the fluorescence spectra can be expressed as [4] : The shape of PL spectrum is mainly determined by the vibrational transition probability. For the i-th mode, when the initial vibrational level is 0, its transition probability to vibrational level ν at ground state can be expressed as:

Which is also called Franck-Condon factor, and here Si is Huang-Rhys factor, which represents the vibronic coupling strength:

And ΔQi represents the displacement along the normal mode (NM)i between the equilibrium positions of the two electronic states.

For the high-frequency vibration modes, the vibronic couplings are generally weak, such as the largest couplings 0.170 and 0.215 for SFFCz and SBPhFCz, respectively. In weak coupling case (S<1), the 0-1 transition probability increase with the coupling increasing.

Here the 0-1 transition for SBPhFCz is just slightly stronger than SFFCz (see Figure S6) due to the slightly larger vibronic coupling. For the low-frequency modes, the vibronic couplings could be very strong, such as the largest couplings 19.0 and 4.84 for SFFCz and SBPhFCz