pith. sign in

arxiv: 2505.11082 · v4 · submitted 2025-05-16 · 💻 cs.CC · cs.DM

Complexity of Firefighting on Graphs

Julius Althoetmar , Jamico Schade , Torben Sch\"urenberg This is my paper

Pith reviewed 2026-05-22 15:25 UTC · model grok-4.3

classification 💻 cs.CC cs.DM
keywords firefightingNP-hardnessgraph gamespursuit-evasionstrategy lengthbinary treeshunter and rabbit
0
0 comments X

The pith

Deciding whether a given number of firefighters can contain a spreading fire on a graph is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines a game on undirected graphs in which fire spreads synchronously from an initial vertex while firefighters protect nodes each round. It proves that computing the minimum number of firefighters sufficient to save the graph is NP-hard and that the shortest winning sequences of moves can require superpolynomial length. These results are first shown for the firefighting process itself and then transferred via a reduction to the Hunter and Rabbit pursuit-evasion game. Almost sharp bounds on the firefighter number are also given for complete binary trees.

Core claim

The decision problem of whether ffn(G) is at most a given integer m is NP-hard, and there exist graphs for which every shortest firefighting strategy has length superpolynomial in the number of vertices, leaving membership in NP unresolved.

What carries the argument

ffn(G), the smallest number of firefighters sufficient to prevent fire from reaching every node when placed one per round under the standard synchronous spread rule.

If this is right

  • The firefighting problem is unlikely to admit an efficient algorithm for arbitrary graphs unless P equals NP.
  • Even when the firefighter number is known to be small, finding a shortest winning strategy may be computationally intractable.
  • The same hardness and length lower bounds carry over directly to the Hunter and Rabbit game on graphs.
  • For the special case of complete binary trees the firefighter number lies between two explicit linear functions of the height.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Parameterized algorithms that fix the firefighter number or the treewidth might still yield practical solutions on restricted graph classes.
  • The superpolynomial strategy length suggests that any exact solver must be prepared to explore exponentially long move sequences in the worst case.
  • Similar reductions could be attempted for other synchronous protection or contamination games on graphs.

Load-bearing premise

Fire spreads in discrete rounds to all unprotected neighboring nodes after each round of firefighter placement.

What would settle it

A polynomial-time algorithm that correctly answers whether ffn(G) <= m for arbitrary graphs G and integers m, or an explicit family of graphs whose shortest winning strategies all have polynomial length.

Figures

Figures reproduced from arXiv: 2505.11082 by Jamico Schade, Julius Althoetmar, Torben Sch\"urenberg.

Figure 1
Figure 1. Figure 1: Two firefighters try to extinguish a partially burning tree. Visualization of the extinguishing [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Decomposing a subset of a complete binary tree into multiple complete binary trees of varying [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Gadget graph H(G, T) with the property that there is a T-winning m-strategy for G if and only if ffn(H(G, T)) ≤ 4m. The blocks X, Y, Z are 2m-cliques and every P j i and the blocks A, B are m-cliques. An edge between two blocks B1 and B2 in this image corresponds to connecting every node in B1 to every node in B2. Proving that FireFighting is NP-hard also implies that FireFighting on digraphs is NP-hard, s… view at source ↗
Figure 4
Figure 4. Figure 4: Construction of G. Every Ti is an arbitrary tree with ai + s nodes. 6 Graphs with Long Shortest Strategies After proving that the problems FireFighting and FireFightingInTime are NP-hard, a naturally arising question is whether these problems are in NP, i.e., whether there exists a polynomial certificate for yes-instances. A natural candidate for such a certificate would be a winning m-strategy (resp. winn… view at source ↗
Figure 5
Figure 5. Figure 5: When a thick edge connects two subgraphs A and B, then every node in A is connected to [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: G′ = (V ′ , E′ ) arises from G = (V, E) by replacing each edge e ∈ E with |V | + 1 many disjoint paths, each with one intermediate node. Note that G′ is bipartite. hunter strategy F ′′ = (F ′ 1 ∩ V, . . . , F′ n′ ∩ V ) is also a winning hn(G′ )-hunter strategy on G′ . The even and odd substrategies (F ′′ 2i )i∈[⌊n′/2⌋] and (F ′′ 2i−1 )i∈[⌈n′/2⌉] are both winning hn(G′ )-firefighter strategies on G, since B… view at source ↗
Figure 7
Figure 7. Figure 7: Lemma 7: Gm is constructed from a m-clique and a path with m nodes The node set Wi (colored in blue) has only one adjacent node. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Decomposing a subset of a complete binary tree into multiple complete binary trees of varying [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Illustration of nodes in the set C1, . . . , C5. The middle node is in the corresponding set Ci , nodes in S are colored blue. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Step 1 of a winning 4m-strategy for H(G, T) if G is 2m-winning in time T. Start by covering A and B in each time step, clearing the paths Pi one by one. The last time step of this process is visualized here. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Step 2: Covering A, B and X. A B X Y Z G P 1 1 P 2 1 P T 1 P T+1 1 P1 P 1 2T+2 P 2 2T+2 P T 2T+2 P T+1 2T+2 P2t+2 [PITH_FULL_IMAGE:figures/full_fig_p023_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Step 3: Covering X and Y . 23 [PITH_FULL_IMAGE:figures/full_fig_p023_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Step 4: Covering Y for T timesteps, while clearing G with the remaining 2m firefighters. In the meantime, the fire is spreading along the paths. The last of the T time steps is visualized. A B X Y Z G P 1 1 P 2 1 P T 1 P T+1 1 P1 P 1 2T+2 P 2 2T+2 P T 2T+2 P T+1 2T+2 P2t+2 [PITH_FULL_IMAGE:figures/full_fig_p024_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Step 5: Covering Y and Z. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Step 6: Covering A, B and Z right before the fire can spread again back to X. A B X Y Z G P 1 1 P 2 1 P T 1 P T+1 1 P1 P 1 2T+2 P 2 2T+2 P T 2T+2 P T+1 2T+2 P2t+2 [PITH_FULL_IMAGE:figures/full_fig_p025_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Step 7: Finally covering A and B while clearing all paths again. The last time step is visualized, after which all nodes are extinguished. Next, we assume that there is no m-strategy for G that wins in time T. We consider the following node subsets: Ω1 = H(G, T) \ (A∪P), Ω2 = H(G, T) \ (G∪P), Ω3 = G∪B ∪Y ∪Z ∪ S i∈[2T +2] P T +1 i , Ω4 = B ∪ Y ∪ Z ∪ Pk ∪ Pℓ ∪ {v}, Ω5 = A ∪ B ∪ Y ∪ Z ∪ Pk ∪ Pℓ, Ω6 = A ∪ B ∪… view at source ↗
Figure 17
Figure 17. Figure 17: For any subset of burning nodes that is Ωn-blocked for some n ∈ [7], the subset of burning nodes will be Ωn′ -blocked after finitely many steps, for some n ′ ∈ [7] with an edge (Ωn, Ωn′ ) or n ′ = n. Case 1.1: Et+1 contains a node v from G. Then Y ∪ {v} ⊆ Ft+1. The only helpful thing one can do with the remaining 2m−1 firefighters is to guard B. Thus, Bt+1 ⊇ H(G, T)\P and hence is Ω2-blocked. Case 1.2: Et… view at source ↗
Figure 18
Figure 18. Figure 18: Construction of G. Every Ti is an arbitrary tree with ai + s nodes. First, if there exists a 3-partition (i1, i′ 1 , i′′ 1 ), . . . ,(ik, i′ k , i′′ k ) of a1, . . . , a3k such that ij , i′ j , i′′ j ∈ [3k], then S = (Ti1 ∪ Ti ′ 1 ∪ Ti ′′ 1 ∪ {c}, . . . , Tik ∪ Ti ′ k ∪ Ti ′′ k ∪ {c}) is a winning ( s k + 3s + 1)-strategy of length k. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_18.png] view at source ↗
read the original abstract

We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters required by ffn(G) and provide almost sharp bounds to this graph parameter for complete binary trees. We show that deciding whether ffn(G) <= m for given G and m is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the problem is in NP. We provide a construction that allows for transferring these results to a well-established Cops and Robbers variant called the "Hunter and Rabbit game".

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper examines the firefighter problem on undirected graphs, where ffn(G) denotes the minimum number of firefighters needed to contain a fire. It establishes nearly tight bounds on ffn for complete binary trees, proves that deciding whether ffn(G) ≤ m is NP-hard via a reduction, shows that shortest containing strategies can require superpolynomial length via an explicit graph family, and transfers the results to the Hunter and Rabbit game variant.

Significance. If the central claims hold, the work provides a useful complexity-theoretic analysis of a standard pursuit-evasion model. Credit is due for the explicit gadget construction underlying the NP-hardness result and the concrete family of graphs establishing the superpolynomial length lower bound; these are load-bearing and falsifiable contributions rather than abstract existence arguments. The extension to the Hunter and Rabbit game broadens applicability. The open question on membership in NP is stated clearly.

minor comments (3)
  1. [Abstract] Abstract: the qualifier 'almost sharp' for the tree bounds would be clearer if the precise multiplicative or additive gap between the upper and lower bounds were stated explicitly rather than left implicit.
  2. [Preliminaries] The definition of the synchronous spread rule and protection semantics (used in both the hardness reduction and length construction) should be restated in a dedicated preliminary section with a small illustrative example to aid readers unfamiliar with the model.
  3. [Introduction] Notation: the symbol ffn(G) is introduced without an explicit comparison to the more common ff(G) or f(G) used in prior literature; a brief remark on the choice would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The referee's summary correctly identifies the main contributions, including the nearly tight bounds for complete binary trees, the NP-hardness reduction, the explicit construction showing superpolynomial strategy length, and the transfer to the Hunter and Rabbit game. We appreciate the recognition given to the concrete gadget and graph family as load-bearing contributions.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes NP-hardness of deciding ffn(G) <= m via a standard reduction from an NP-complete problem using explicit graph gadget constructions that encode placements as blocking choices. The superpolynomial strategy length is shown by an explicit infinite family of graphs forcing exponential rounds. These steps rely on the synchronous spread model defined in the paper and external combinatorial constructions, with no self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the central claims to the paper's own inputs by construction. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard definition of the firefighting game and basic graph-theoretic assumptions; no free parameters, invented entities, or ad-hoc axioms are introduced beyond the game rules.

axioms (1)
  • domain assumption Fire spreads synchronously to all unprotected adjacent nodes each round after firefighter placement.
    This timing and protection rule is the standard model for the firefighting game and is required for both the hardness reduction and the length lower bound.

pith-pipeline@v0.9.0 · 5627 in / 1296 out tokens · 66218 ms · 2026-05-22T15:25:48.316610+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Abramovskaya, Fedor V

    Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, and Michał Pilipczuk. How to hunt an invisible rabbit on a graph.European Journal of Combinatorics, 52:12–26, 2016.doi: 10.1016/j.ejc.2015.08.002

    work page doi:10.1016/j.ejc.2015.08.002 2016

  2. [2]

    Searching and sweeping graphs: A brief survey.Le Matematiche, 59:5–37, 2006

    Brian Alspach. Searching and sweeping graphs: A brief survey.Le Matematiche, 59:5–37, 2006. URL:https://api.semanticscholar.org/CorpusID:15575799

    work page 2006

  3. [3]

    Time constrained graph searching

    Brian Alspach, Danny Dyer, Denis Hanson, and Boting Yang. Time constrained graph searching. Theoretical Computer Science, 399(3):158–168, 2008. Graph Searching.doi:10.1016/j.tcs.2008. 02.035

    work page doi:10.1016/j.tcs.2008 2008

  4. [4]

    Hunting a rabbit is hard, 2025.arXiv:2502.15982

    Walid Ben-Ameur, Harmender Gahlawat, and Alessandro Maddaloni. Hunting a rabbit is hard, 2025.arXiv:2502.15982

    work page arXiv 2025

  5. [5]

    Complexity results for a cops and robber game on directed graphs.Networks, 86(2):144–156, 2025.doi:10.1002/net.22284

    Walid Ben-Ameur and Alessandro Maddaloni. Complexity results for a cops and robber game on directed graphs.Networks, 86(2):144–156, 2025.doi:10.1002/net.22284

    work page doi:10.1002/net.22284 2025

  6. [6]

    Searching for an intruder on graphs and their subdi- visions.Electron

    Anton Bernshteyn and Eugene Eu-Juin Lee. Searching for an intruder on graphs and their subdi- visions.Electron. J. Comb., 29, 2021.doi:10.37236/10577

    work page doi:10.37236/10577 2021

  7. [7]

    Hunting rabbits on the hypercube.Discret

    Jessalyn Bolkema and Corbin Groothuis. Hunting rabbits on the hypercube.Discret. Math., 342:360–372, 2017.doi:10.1016/j.disc.2018.10.011

    work page doi:10.1016/j.disc.2018.10.011 2017

  8. [8]

    A survey of graph burning.Contributions to Discrete Mathematics, 16, 03 2021

    Anthony Bonato. A survey of graph burning.Contributions to Discrete Mathematics, 16, 03 2021. doi:10.11575/cdm.v16i1.71194

    work page doi:10.11575/cdm.v16i1.71194 2021

  9. [9]

    Anthony Bonato and Richard Nowakowski.The Game of Cops and Robbers on Graphs. 09 2011. doi:10.1090/stml/061

    work page doi:10.1090/stml/061 2011

  10. [10]

    Springer New York, New York, NY, 2013.doi:10.1007/978-1-4419-7997-1_76

    Anthony Bonato and Boting Yang.Graph Searching and Related Problems, pages 1511–1558. Springer New York, New York, NY, 2013.doi:10.1007/978-1-4419-7997-1_76

    work page doi:10.1007/978-1-4419-7997-1_76 2013

  11. [11]

    Finding a princess in a palace: a pursuit-evasion problem.The Electronic Journal of Combinatorics, 20, 04 2012.doi:10.37236/2296

    John Britnell and Mark Wildon. Finding a princess in a palace: a pursuit-evasion problem.The Electronic Journal of Combinatorics, 20, 04 2012.doi:10.37236/2296

    work page doi:10.37236/2296 2012

  12. [12]

    The minimal regular graph containing a given graph.Ameri- can Mathematical Monthly, 70:1074, 1963

    Paul Erdös and Paul Joseph Kelly. The minimal regular graph containing a given graph.Ameri- can Mathematical Monthly, 70:1074, 1963. URL:https://api.semanticscholar.org/CorpusID: 124944769

    work page 1963

  13. [13]

    The firefighter problem: a survey of results, directions and questions.Australas

    Stephen Finbow and Gary MacGillivray. The firefighter problem: a survey of results, directions and questions.Australas. J Comb., 43:57–78, 2009. URL:http://ajc.maths.uq.edu.au/pdf/43/ajc_ v43_p057.pdf

    work page 2009

  14. [14]

    Masset, R

    Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, and Karol Suchan. Pursuing a fast robber on a graph.Theoretical Computer Science, 411(7):1167–1181, 2010.doi:10.1016/j. tcs.2009.12.010

    work page doi:10.1016/j 2010

  15. [15]

    Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

    Fedor V. Fomin and Dimitrios M. Thilikos. An annotated bibliography on guaranteed graph search- ing.Theoretical Computer Science, 399(3):236–245, 2008. Graph Searching.doi:10.1016/j.tcs. 2008.02.040

    work page doi:10.1016/j.tcs 2008

  16. [16]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990

    work page 1990

  17. [17]

    Catching a mouse on a tree.arXiv: Combinatorics, 2015

    Vytautas Gruslys and Ares M’eroueh. Catching a mouse on a tree.arXiv: Combinatorics, 2015. URL:https://api.semanticscholar.org/CorpusID:117260205

    work page 2015

  18. [18]

    Cops, robbers and graphs.Tatra Mountains Mathematical Publications, 36, 01 2007

    Gena Hahn. Cops, robbers and graphs.Tatra Mountains Mathematical Publications, 36, 01 2007

    work page 2007

  19. [19]

    An evasion game on a graph.Discrete Mathematics, 314:1–5, 2014.doi:10.1016/ j.disc.2013.09.004

    John Haslegrave. An evasion game on a graph.Discrete Mathematics, 314:1–5, 2014.doi:10.1016/ j.disc.2013.09.004. 12

    work page 2014

  20. [20]

    On the computational complexity of a game of cops and robbers.Theoretical Computer Science, 477:48–56, 2013.doi:10.1016/j.tcs.2012.11.041

    Marcello Mamino. On the computational complexity of a game of cops and robbers.Theoretical Computer Science, 477:48–56, 2013.doi:10.1016/j.tcs.2012.11.041

    work page doi:10.1016/j.tcs.2012.11.041 2013

  21. [21]

    Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.doi:10.1016/S0022-0000(70) 80006-X

    work page doi:10.1016/s0022-0000(70 1970

  22. [22]

    Optimalembeddingofatreeintoanintervalgraphinlineartime

    PetraScheffler. Optimalembeddingofatreeintoanintervalgraphinlineartime. InJaroslavNeˆ setril and Miroslav Fiedler, editors,Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, volume 51 ofAnnals of Discrete Mathematics, pages 287–291. Elsevier, 1992.doi: 10.1016/S0167-5060(08)70644-7

    work page doi:10.1016/s0167-5060(08)70644-7 1992

  23. [23]

    Vertex-to-vertex search in a graph

    Ratko Tošić. Vertex-to-vertex search in a graph. InProceedings of the Sixth Yugoslav Seminar on Graph Theory, pages 233–237. University of Novi Sad, 1985. 13 A Appendix A.1 Omitted Proofs of Section 3: Basic Properties and Bounds We start by giving the missing proofs of the upper and lower bounds on the firefighter number. Lemma 1(Lower Bounds).LetG= (V, ...

    work page 1985

  24. [24]

    2.δ min(G)≥m−1, i.e., each node inGhas at leastm−1neighbours

    There exists ani∈[|V| −m+ 1]such that anyW⊆Vwith|W|=ifulfills|N(W)| ≥m−1. 2.δ min(G)≥m−1, i.e., each node inGhas at leastm−1neighbours

    work page

  25. [25]

    4.|E| ≥m·(|V| − m+1 2 )

    There exists aG′ ⊆Gwith ffn(G ′)≥m. 4.|E| ≥m·(|V| − m+1 2 ). Proof of 2.Follows directly by Lemma 1.1 fori= 1. An intuitive proof is the following: IfB t =V and we use at mostm−1firefighters, then each node in ˜Et =B t \F t has at least one provisionally burning neighbour left, since at mostm−2of its at leastm−1neighbours can also be inF t. Hence, Bt+1 =B...

    work page

  26. [26]

    2.Gis a tree with diam(G)≤2m−2

    pw(G) + 1≤m, where pw(G)denotes the pathwidth ofG. 2.Gis a tree with diam(G)≤2m−2

    work page

  27. [27]

    Proof of 2.We prove this by induction

    There exists a graphGk = (Vk, Ek)fork∈N ≥0 with ffn(Gk)≤m−k,G k ⊆Gand|V k| ≥ |V| −k. Proof of 2.We prove this by induction. Form= 1,Gcan only consist of a single node, so ffn(G)≤1is obvious. Next, we assume that the statement holds for somem∈N>0, i.e., any treeTwith diam(T)≤ 2m−2satisfies ffn(T)≤m. LetGbe a tree with diam(G)≤2(m+ 1)−2 = 2m. First, we choo...

    work page

  28. [28]

    Every complete binary treeT= (V, E)hasmax v∈V δ(v)≤3≤dand can therefore be extended to ad-regularG ′ for everyd∈N ≥3, see [12]

    Letd >3. Every complete binary treeT= (V, E)hasmax v∈V δ(v)≤3≤dand can therefore be extended to ad-regularG ′ for everyd∈N ≥3, see [12]. According to Theorem 1, complete binary trees can have arbitrarily high firefighter values. Lemma 1.3 implies that the same holds forG′. Furthermore, ad-regular graphGhasmin v∈V δ(v) =dand Lemma 1.2 implies ffn(G)≥d+ 1. ...

    work page

  29. [29]

    Together with Lemma 2.1, this implies the claim

    + 1. Together with Lemma 2.1, this implies the claim. As a short overview, the following table lists for some common graph parameters whether they can, in general, be used to find an upper or lower bound on the firefighter number. We split the statements into several lemmata and prove them separately. Graph parameter Upper bound on ffn Lower bound on ffn ...

    work page

  30. [30]

    Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010

    0| {z } y+3digits . Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010. . .1| {z } d−y−2digits

    work page

  31. [31]

    10| {z } d+1digits = 1010

    0| {z } y+3digits −1010. . .10| {z } d+1digits = 1010. . .10110| {z } y+1digits , which contradicts the fact that|x|hasydigits. Hence, the first(d−y−1)digits have to remain alternating ones and zeros. This also implies that there has to appear a one in the last2 +ydigits, since there is no way to remove it without altering the(3 +y)-th digit. Therefore we...

    work page

  32. [32]

    Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010

    1| {z } y+4digits . Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010. . .10| {z } d+1digits −1010. . .10| {z } d−y−3digits

    work page

  33. [33]

    1011| {z } y+2digits , which contradicts the fact that|x|hasydigits

    1| {z } y+4digits = 10. . .1011| {z } y+2digits , which contradicts the fact that|x|hasydigits. Hence, the first(d−y−1)digits have to remain alternating ones and zeros. Moreover, the lasty+2digits cannot all be zero, since that would implyx=−10. . .10| {z } y+2digits , again contradicting the number of digits of|x|. Therefore we have at leastd−y−1 =d− ⌊lo...

    work page

  34. [34]

    Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010

    0| {z } y+4digits . Thus, in order to change any of the first d−y−1digits, we would need |x| ≥1010. . .1| {z } d−y−3digits

    work page

  35. [35]

    10| {z } d+1digits = 10

    0| {z } y+4digits −1010. . .10| {z } d+1digits = 10. . .10110| {z } y+2digits , which contradicts the fact that|x|hasydigits. Hence, the firstd−y−1digits remain alternating ones and zeros. This also implies that there has to appear a one in the last2 +ydigits, since there is no way to remove it without altering the(3+y)-th digit. Therefore we have at leas...

    work page

  36. [36]

    Thus, in order to change any of the first 20 d−y−1digits, we would need |x| ≥1010

    1| {z } y+3digits . Thus, in order to change any of the first 20 d−y−1digits, we would need |x| ≥1010. . .10| {z } d+1digits −1010. . .10| {z } d−y−2digits

    work page

  37. [37]

    1011| {z } y+1digits , which contradicts the fact that|x|hasydigits

    1| {z } y+3digits = 10. . .1011| {z } y+1digits , which contradicts the fact that|x|hasydigits. Hence, the first(d−y−1)digits have to remain alternating ones and zeros. Moreover, the lasty+2digits cannot all be zero, since that would implyx=−10. . .10| {z } y+1digits , again contradicting the number of digits of|x|. Therefore we have at leastd−y−1 =d− ⌊lo...

    work page