1038 A10s Fit into One A0

Friedrich, Noel

doi:10.4230/LIPIcs.FUN.2026.18

1038 A10s Fit into One A0

Noel Friedrich

Department of Mathematics, ETH Zürich, Switzerland

Abstract

The A-series paper sizes are specified in integer millimetres in ISO 216. Since the sizes are based on an irrational aspect ratio, rounding errors introduce small but cumulative discrepancies from their nominal areas. In this work, we prove that exactly 1038 sheets of ISO A10 can be packed without overlap into a single ISO A0 sheet, allowing only orthogonal (axis-aligned) placements. A lower bound is given by an explicit construction, while the upper bound is proved by a simple-to-verify computer-assisted certificate. Along the way, the dual certificates produce unexpectedly pretty weightmaps.¹¹1Companion video (expository): https://youtu.be/zDKBCIMkDbw [10]

Keywords and phrases:

rectangle packing, pallet loading problem, rounding effects, ISO 216

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Packing and covering problems

Supplementary Material:

Software (Verification scripts, rounded weightmap certificate, and packing coordinates): https://doi.org/10.5281/zenodo.18813570

DOI:

10.4230/LIPIcs.FUN.2026.18

Event:

13th International Conference on Fun with Algorithms (FUN 2026)

Editor:

John Iacono

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

There are many reasons why the A-series has become the dominant international system for paper sizes [17]: it is metrically grounded, self-similar and built around the elegant aspect ratio $1:\sqrt{2}$ [12]. Yet, ISO 216 [6] (and its predecessor DIN 476 [11]) specify the actual paper sizes in whole millimetres. Since the nominal side ratio is irrational, this discretization introduces a rounding error. In the standard construction, A0 is approximated first, and each subsequent size is obtained by halving the previous one and rounding down so that two sheets of $A(n)$ can always be cut from one sheet of $A(n-1)$ [14]. In this work we quantify the cumulative effect of these roundings by studying a concrete packing problem: how many A10 sheets can be placed, without overlap and with axis-aligned orientation, inside a single sheet of A0?

To formalise this, let us fix integers $(L,W):=(1189,841)$ and $(a,b):=(37,26)$ to be the sizes of the A0 and A10 rectangles in millimetre units. We further define an integer coordinate system where the top-left corner represents $(0,0)$ and the bottom-right corner of the larger A0-sized rectangle represents $(L,W)$ .

Definition 1 (Orthogonal placement and packing).

An orthogonal placement is a rectangle $R=[x,x+w]\times[y,y+h]\subseteq[0,L]\times[0,W]$ where $(w,h)\in\{(a,b),(b,a)\}$ and $x,y\in\mathbb{R}$ (or $x,y\in\mathbb{Z}$ in the integer-mm model).

A set $\mathcal{P}$ of orthogonal placements is a non-overlapping orthogonal packing if for any two distinct rectangles $R,R^{\prime}\in\mathcal{P}$ , their interiors are disjoint, i.e., $\mathrm{int}(R)\cap\mathrm{int}(R^{\prime})=\emptyset$ (Equivalently, rectangles may touch at boundaries but may not overlap in area).

Definition 2 (Optimal packing number).

Let $\operatorname{OPT}(L,W,a,b)$ be the maximum size of a non-overlapping orthogonal packing of $(a\times b)$ -rectangles into an $(L\times W)$ -rectangle. In this article, we study $\operatorname{OPT}:=\operatorname{OPT}(1189,841,37,26)$ .

Without much work, we can show some lower and upper bounds for $\operatorname{OPT}$ .

Proposition 3 (Trivial bounds).

$\operatorname{OPT}\in\{1024,\dots,1039\}\subseteq\mathbb{N}$ .

Proof.

The lower bound of $1024=2^{10}$ holds because the paper sizes are designed such that every sheet of $A(n)$ can fit (at least) two sheets of $A(n+1)$ for $0\leq n\leq 9$ [6]. The upper bound holds by area: $\operatorname{OPT}\leq\left\lfloor\frac{\text{Area of A0}}{\text{Area of A10}}% \right\rfloor=\left\lfloor\frac{1189\times 841}{37\times 26}\right\rfloor=1039$ . $\hfill\blacktriangleleft$

Our primary goal in this article is proving the exact value of $\operatorname{OPT}$ , namely:

Theorem 4 (Main Theorem, computer-assisted).

$\operatorname{OPT}=1038$ .

The proof of Theorem 4 will be done in three steps. We will first show that we can assume the integer-mm model without loss of generality. Then we will provide an explicit packing of size 1038, hence proving a lower bound. Finally, we will show an upper bound of 1038 using a computer-assisted argument, concluding the proof.

Lemma 5 (Integer-coordinates without loss of generality).

Consider an orthogonal packing of axis-aligned rectangles of sizes $(a\times b)$ and $(b\times a)$ inside the container $[0,L]\times[0,W]$ , where rectangle positions may use arbitrary real coordinates.

Then there exists an orthogonal packing of the same cardinality in which every rectangle has integer coordinates, i.e., each rectangle is of the form $[x,x+w]\times[y,y+h]$ with $x,y\in\mathbb{Z}$ and $(w,h)\in\{(a,b),(b,a)\}$ .

Proof.

Consider an arbitrary orthogonal packing $\mathcal{P}=\{R_{1},\dots,R_{n}\}$ of size $n$ . We first make this packing left-stable by repeatedly selecting any rectangle $R\in\mathcal{P}$ and translating it leftwards, i.e., decreasing its $x$ -coordinate $x(R)$ , as far as possible while keeping the packing non-overlapping and $x(R)\geq 0$ . This process terminates at a packing in which every rectangle is either touching the boundary ( $x(R)=0$ ) or its left side touches the right side of another rectangle.

The resulting left-stable packing is still non-overlapping and has the same size $n$ . Furthermore, every rectangle must either have an $x$ -coordinate of $x(R)=0$ (on the boundary) or $x(R)=x(R^{\prime})+w(R^{\prime})$ where $R^{\prime}$ is a rectangle blocking leftwards movements and $w(R^{\prime})$ is the width of said rectangle. Since we can form a chain of blocking rectangles from every rectangle to the line $x=0$ and since $w(R)\in\mathbb{Z}$ for all rectangles $R\in\mathcal{P}$ , all $x(R)$ must be integer.

We can apply an analogous argument for producing a top-stable packing that will yield integer $y$ -coordinates. Therefore, there exists a feasible packing of the same size whose rectangle coordinates are integers. $\hfill\blacktriangleleft$

2 Lower Bound

Theorem 6 (Lower bound).

$\operatorname{OPT}\geq 1038$ .

We will prove this by splitting the $L\times W$ area into two parts. Part A is $962\times 841$ , Part B is $227\times 841$ . Combined, these two parts exactly cover the entire $(962+227)\times 841=L\times W$ area. An explicit construction for both parts is depicted in Figure 1.

Figure 1: An arrangement for 1038 A10 in one A0, constructed on a custom website (FORP [7]).

Lemma 7 (Part A).

A $(962\times 841)$ rectangle can be packed gaplessly with a non-overlapping orthogonal packing of size $841$ , i.e., $\operatorname{OPT}(962,W,a,b)=841$ .

Proof.

Since $15\cdot 37+11\cdot 26=841$ , we tile the height by $15$ strips of height $37$ and $11$ strips of height $26$ . Each $37$ -high strip is tiled by $37$ upright $(26\times 37)$ rectangles as $37\cdot 26=962$ . Each $26$ -high strip is tiled by $26$ horizontal $(37\times 26)$ rectangles as $26\cdot 37=962$ .

Thus the $(962\times 841)$ rectangle is tiled gaplessly by $15\cdot 37+11\cdot 26=841$ rectangles, implying $\operatorname{OPT}(962,841,a,b)\geq 841$ . Equality follows directly from the lack of gaps. $\hfill\blacktriangleleft$

Lemma 8 (Part B).

A $(227\times 841)$ rectangle can be packed with a non-overlapping orthogonal packing of size $197$ , i.e., $\operatorname{OPT}(227,W,a,b)\geq 197$ .

Proof.

Appendix A lists $197$ rectangles by integer coordinates $(x_{0},y_{0},x_{1},y_{1})$ , representing $R=[x_{0},x_{1}]\times[y_{0},y_{1}]$ . It suffices to check:

(i)

Correct dimensions: for every listed rectangle, $(x_{1}-x_{0},y_{1}-y_{0})\in\{(26,37),(37,26)\}$ .
(ii)

Containment: for every listed rectangle, $0\leq x_{0}<x_{1}\leq 227$ and $0\leq y_{0}<y_{1}\leq 841$ .
(iii)

Non-overlap: the rectangles are pairwise interior-disjoint. A fun way to verify this (using integrality of the coordinates) is to count covered unit squares: if we mark every covered $1\times 1$ cell in the $227\times 841$ grid, then disjointness is equivalent to the number of covered cells being exactly the sum of areas, i.e., $197\cdot 37\cdot 26$ .

Therefore the listed rectangles form a non-overlapping orthogonal packing of size $197$ in the $(227\times 841)$ container, proving $\operatorname{OPT}(227,841,a,b)\geq 197$ . The appendix also contains a short script for verifying these claims mechanically. Combined with Lemma 7, this proves Theorem 6. $\hfill\blacktriangleleft$

This specific packing was constructed and exported using a custom website featuring an interactive visualization and playground we developed for this problem appropriately called Fun Orthogonal Rectangle Packing [7]. The presented arrangements were constructed by hand and by using an existing algorithm developed by Birgin, Lobato and Morabito [4] for smaller subproblems.

3 Upper Bound

Existing techniques for finding upper bounds use a structural approach [15] on a Minimum Size Instance (MSI) [16]. The MSI is a minimal instance preserving the same set of optimal packing arrangements. In this setting, our packing problem can be formulated as the $(L,W,a,b)=(1189,841,37,26)$ instance of the Pallet Loading Problem (PLP).

Our instance is already the MSI, since A0 can be tiled gaplessly by A10s in both width and height: $23\cdot 37+13\cdot 26=1189$ and $15\cdot 37+11\cdot 26=841$ . The Barnes bound [3] for this instance also yields 1039. Together, both of these facts indicate that this instance does not permit an easy simplification. Therefore, we need to employ more complex computational bounds.

3.1 Structural LP Bounds (that almost work)

Isermann [13] and Nelißen [18] show how we can compute upper bounds by considering $a\times 1$ and $b\times 1$ strips combined with structural information about all possible feasible partitions of the side lengths, expressed by the following linear program:

F(L,a,b):=\{(i,j)\in\mathbb{Z}_{\geq 0}^{2}\mid ia+jb\leq L,\ (i,j)\neq(0,0)\},

F(W,a,b):=\{(f,g)\in\mathbb{Z}_{\geq 0}^{2}\mid fa+gb\leq W,\ (f,g)\neq(0,0)\}.

	$\displaystyle\max$	$\displaystyle\sum_{(i,j)\in F(L,a,b)}\frac{i}{b}\,x_{ij}+\sum_{(f,g)\in F(W,a,% b)}\frac{f}{b}\,y_{fg}$
	s.t.	$\displaystyle\sum_{(i,j)\in F(L,a,b)}x_{ij}\leq W,\qquad\sum_{(f,g)\in F(W,a,b% )}y_{fg}\leq L,$
		$\displaystyle a\sum_{(i,j)\in F(L,a,b)}i\,x_{ij}-b\sum_{(f,g)\in F(W,a,b)}g\,y% _{fg}=0,$
		$\displaystyle b\sum_{(i,j)\in F(L,a,b)}j\,x_{ij}-a\sum_{(f,g)\in F(W,a,b)}f\,y% _{fg}=0,$
		$\displaystyle x_{ij}\geq 0\quad\forall(i,j)\in F(L,a,b),\qquad y_{fg}\geq 0% \quad\forall(f,g)\in F(W,a,b).$

We formulated and ran this linear program using the Gurobi LP solver, which computed an optimum of 1039.0254329004. This structural bound does not disprove 1039, but is close enough to yield hope that some clever tweaks might drop this bound below 1039. Unfortunately, we did not manage to improve this bound, even when employing more advanced constraints suggested by Nelißen [18] and Letchford [15]. This supports the earlier claim that our specific instance of the PLP does not permit a simple proof of optimality.

3.2 Weighing Bounds (a.k.a. dual witnesses)

The aforementioned structural bounds can be expressed in a simpler way by reformulating them as weightmap-bounds. The idea is to find a weightmap $w(x,y)$ which maps every $1\times 1$ square on the A0-sized lattice to a non-negative real value. If we construct a weightmap such that for every possible rectangle placement the sum over that rectangle is $\geq 1$ , the total sum over all weights is then an upper bound for the optimal packing size.

We formalize this by defining the set of all integer placements:

	$\displaystyle\mathcal{R}_{horizontal}$	$\displaystyle=\{(x,y,a,b)\mid 0\leq x\leq L-a,\ 0\leq y\leq W-b\},$
	$\displaystyle\mathcal{R}_{vertical}$	$\displaystyle=\{(x,y,b,a)\mid 0\leq x\leq L-b,\ 0\leq y\leq W-a\},$
	$\displaystyle\mathcal{R}$	$\displaystyle=\mathcal{R}_{horizontal}\ \cup\ \mathcal{R}_{vertical}.$

Lemma 9 (Weight-map upper bound).

Let $w:\{0,\dots,L-1\}\times\{0,\dots,W-1\}\to\mathbb{R}_{\geq 0}$ . Assume that every placement $(x_{0},y_{0},w,h)\in\mathcal{R}$ satisfies

\sum_{x=x_{0}}^{x_{0}+w-1}\ \sum_{y=y_{0}}^{y_{0}+h-1}w(x,y)\ \geq\ 1.

Then the size of any non-overlapping orthogonal packing is at most

\operatorname{OPT}(L,W,a,b)\leq T:=\sum_{x=0}^{L-1}\sum_{y=0}^{W-1}w(x,y).

Proof.

Let $\mathcal{P}$ be any non-overlapping orthogonal packing. By assumption, every rectangle in $\mathcal{P}$ covers a weight of at least $1$ . Since rectangles in $\mathcal{P}$ are interior-disjoint, the total weight covered by all rectangles is at most the total weight $T$ of the container. Hence $|\mathcal{P}|\leq T$ . $\hfill\blacktriangleleft$

Corollary 10 (Scaled integer certificate).

Let $S\in\mathbb{Z}_{\geq 1}$ and let $w:\{0,\dots,L-1\}\times\{0,\dots,W-1\}\to\mathbb{Z}_{\geq 0}$ . If every placement in $\mathcal{R}$ has weight at least $S$ and $\sum_{x,y}w(x,y)<1039\cdot S$ , then $\operatorname{OPT}\leq 1038$ .

Proof.

Apply Lemma 9 to the scaled weightmap $w/S$ . $\hfill\blacktriangleleft$

The space of all weightmaps is quite large (there are approximately 1 million variable weights and approximately 2 million possible rectangle placements) and hence computationally expensive to optimize for directly. If we restrict the weightmaps to specific (easier to compute) forms, we can recover some structural bounds.

Refer to caption — Figure 2: The optimal weightmap under restriction $w(x,y)=a_{x}+b_{y}$ .

For example, restricting to weightmaps of the form $w(x,y)=a_{x}+b_{y}$ severely limits the space of free variables to only $L+W=2030$ . Optimizing over this restricted family yields the familiar value 1039.0254329004 (Figure 2), i.e., the same bound as the structural LP. We tried several more restricted weightmaps (periodic tilings, diagonal striping patterns, extra border variables and combinations), but all either produced a worse upper bound or collapsed to the striping pattern. This raised the fear that the optimal value of any weightmap approach might not lie below 1039, which would invalidate this proof approach.

We therefore solve the general weightmap LP. To do so efficiently, we use a prefix-sum reformulation that dramatically reduces the number of nonzero constraint coefficients. We introduce variables $F_{x,y}\geq 0$ for $x\in\{1,\dots,L\}$ and $y\in\{1,\dots,W\}$ with boundary convention $F_{0,y}=F_{x,0}=0$ , and solve:

	$\displaystyle\min$	$\displaystyle F_{L,W}$
	s.t.	$\displaystyle F_{x,y}-F_{x-1,y}-F_{x,y-1}+F_{x-1,y-1}\ \geq 0\qquad\forall\,x% \in\{1,\dots,L\}\ \forall\,y\in\{1,\dots,W\},$
		$\displaystyle F_{x+w,\,y+h}-F_{x,\,y+h}-F_{x+w,\,y}+F_{x,\,y}\ \geq 1\qquad% \forall\,(x,y,w,h)\in\mathcal{R},$
		$\displaystyle F_{x,y}\geq 0\qquad\forall\,x\in\{1,\dots,L\}\ \forall\,y\in\{1,% \dots,W\}.$

This reformulation uses prefix sums over the weights instead of variables for each weight; the individual weights can be reconstructed trivially.

We computed the optimum of this LP using Gurobi (PDHG method). We ran the instance on the Euler Cluster [5]. The computed optimum value is 1038.7291940779483. Since this is an upper bound, this indicates that an orthogonal packing of size 1038 is optimal, but needs to be verified in exact arithmetic to avoid floating-point inaccuracies.

Theorem 11 (Upper bound, computer-assisted).

There exists an integer weightmap $w:\{0,\dots,L-1\}\times\{0,\dots,W-1\}\to\mathbb{Z}_{\geq 0}$ with scale $S=10^{6}$ such that:

(i)

every placement in $\mathcal{R}$ has total weight at least $S$ ,
(ii)

$\sum_{x,y}w(x,y)<1039\cdot S$ .

Consequently, $\operatorname{OPT}\leq 1038$ .

Proof.

We take an optimal floating-point-valued weightmap from the LP above, multiply it by $10^{6}$ and round to integers. Using numerically exact integer addition, we computed a minimum rectangle-sum of $\Sigma_{\min}=1{,}000{,}000$ and a total sum of $\Sigma_{\text{total}}=1{,}038{,}768{,}234$ . Thus condition (i) holds (since $\Sigma_{\min}\geq S$ ) and condition (ii) holds (since $\Sigma_{\text{total}}<1039S$ ). The claim $\operatorname{OPT}\leq 1038$ follows from Corollary 10. $\hfill\blacktriangleleft$

The proof argument used might be considered useful for applications of the PLP, which has many real-world applications, especially in logistics [20], but the general approach of using a weightmap as an upper bound is not entirely novel [15].

3.3 Verifier

The rounded weights are available on the GitHub page [9]. The following script verifies the conditions of Theorem 11 using exact integer arithmetic:

⬇

import numpy as np

weights = np.load("upper-bound/weights/rounded-weights.npy")

assert weights.shape == (1189, 841) and weights.dtype == np.int64

assert weights.min() >= 0

assert weights.sum() < 1039_000_000

# prefix-sum matrix over large rectangle

S = np.zeros((weights.shape[0] + 1, weights.shape[1] + 1), dtype=np.int64)

S[1:, 1:] = weights.cumsum(axis=0).cumsum(axis=1)

def all_rect_sums_at_least(w, h, threshold):

# returns all sums for (w, h) windows as a 2d array

sums = S[w:, h:] - S[:-w, h:] - S[w:, :-h] + S[:-w, :-h]

return sums.min() >= threshold

assert all_rect_sums_at_least(26, 37, 1_000_000) # horizontal

assert all_rect_sums_at_least(37, 26, 1_000_000) # vertical

4 Good-looking weightmaps

The proof technique of generating minimal weightmaps can be applied to other instances of the PLP. By colouring these weightmaps according to their values, we get some good-looking pictures. Figure 4 shows a grid of all computed optimal weightmaps for instances $(64,64,a,b)$ with $1\leq a,b\leq 10$ . The colourmap between weightmaps is not synchronized; a tone of yellow (indicating the highest weight value across a given weightmap) must not always indicate the same weight value as the same tone in another weightmap.

These weights were computed via Gurobi within a numerical precision of $10^{-9}$ . The code used to generate these and other weightmaps can be found in the GitHub repository [9]. Because these pictures look nice and display a surprising number of patterns and complexity, we also present these in a digital art gallery, appropriately called the Gallery of Papel [8]. The Gallery showcases all optimal weightmaps of instances of the form $(S,S,a,b)$ with $64\geq S\geq a\geq b\geq 1$ , hence containing a total number of $\sum_{S=1}^{64}\sum_{a=1}^{S}a=\sum_{S=1}^{64}\frac{S(S+1)}{2}=45760$ weightmaps.

Figure 4: Grid of optimal weightmaps of family of instances

(64,64,a,b)

.

5 Related Work

The PLP, also known as the manufacturer’s pallet loading problem, has been studied extensively; see, e.g., the survey by Silva–Oliveira–Wäscher [19]. Widely used computational benchmarks are given by the Cover I and Cover II instance sets, which contain representatives of equivalence classes with area ratio $(L\cdot W)/(a\cdot b)<51$ and $51\leq(L\cdot W)/(a\cdot b)<101$ respectively [2, 4]. For these datasets, Birgin–Lobato–Morabito report that their combined recursive partitioning approach finds optimal solutions for all Cover I and II instances [4]. Heuristic methods have also been evaluated on these sets and achieve good performance in practice [2].

Our A0/A10 instance has a much larger area ratio, $(1189\cdot 841)/(37\cdot 26)\approx 1039.4$ and is therefore outside the classical benchmark regime. The natural 0–1 formulations for PLP scale with the number of feasible placements (and with the number of unit cells in a discretized model), which can become extremely large for instances with small items [1]. In our case, even in the integer-millimetre model there are on the order of millions of candidate placements, making direct exact optimization approaches impractical.

Direct upper bounds for PLP have also received significant attention. In particular, Nelißen [18] and Letchford–Amaral [15] study structural LP bounds and related dominance relationships between bounds. We implemented these structural bounds for our instance. Unfortunately, they did not yield an upper bound below $1039$ . To our knowledge, the specific ISO 216-motivated instance $(L,W,a,b)=(1189,841,37,26)$ has not previously been studied.

6 Open Questions

While A0 and A10 arguably pose the most interesting packing problem inside the A series of paper sizes (as they have the largest difference), one can ask the same question for $A(n)$ and $A(m)$ for $10\geq n\geq m\geq 0$ .

Table 1: Remaining A series optimal orthogonal packing results.

	A0	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
A0	$=1$	$=2$	$=4$	$=8$	$=16$	$=32$	$=64$	$=128$	${\color[rgb]{0,0,1}=258}$	${\color[rgb]{0,0,1}516\leq x_{1}\leq 518}$	${\color[rgb]{0,0,1}=1038}$
A1		$=1$	$=2$	$=4$	$=8$	$=16$	$=32$	$=64$	${\color[rgb]{0,0,1}=129}$	${\color[rgb]{0,0,1}258\leq x_{2}\leq 259}$	${\color[rgb]{0,0,1}518\leq x_{3}\leq 519}$
A2			$=1$	$=2$	$=4$	$=8$	$=16$	$=32$	$=64$	$=128$	${\color[rgb]{0,0,1}=258}$
A3				$=1$	$=2$	$=4$	$=8$	$=16$	$=32$	$=64$	${\color[rgb]{0,0,1}=129}$
A4					$=1$	$=2$	$=4$	$=8$	$=16$	$=32$	$=64$
A5						$=1$	$=2$	$=4$	$=8$	$=16$	$=32$
A6							$=1$	$=2$	$=4$	$=8$	$=16$
A7								$=1$	$=2$	$=4$	$=8$
A8									$=1$	$=2$	$=4$
A9										$=1$	$=2$
A10											$=1$

We computed solutions to many of these instances and proved optimality in most of these cases using the algorithm presented by Birgin, Lobato and Morabito [4]. This solved all instances except A10 in A0, A9 in A0, A10 in A1 and A9 in A1. For these instances, we computed a simple upper bound using the area bound of the Minimum Size Instance [16] and found good arrangements by hand to prove the lower bounds. Details for these bounds can be found on the GitHub [9]. Naturally, these bounds could be tightened by computing bounds like we presented for A0 and A10. The computed bounds can be seen in Table 1, blue entries correspond to results where the optimum is not a power of two and are thus, in some sense, surprising.

Another question of interest could be the limits of the weightmap proof method. Does there exist an instance $(L,W,a,b)$ of the PLP where the optimal weight does not correspond to the size of an optimal orthogonal packing? We have searched through many smaller instances by computing the optimal weightmaps but have not found a counterexample. The largest difference between the optimal packing size and total weight we were able to find was at instance $(50,50,5,4)$ , where the optimal packing has size 124, but the computed optimal weightmap has a weight-sum of 124.8. Since the large weight-finding LP is dual to the relaxed direct packing-LP [15], they share a common optimal value under strong duality. Hence, this is equivalent to asking whether the LP-relaxation of the packing-LP ever causes a difference $\geq 1$ in optimal value compared to the packing-ILP.

Lastly, Theorem 4 is a statement about orthogonal packings. It seems unlikely that allowing non- $90^{\circ}$ rotations would make a packing of size 1039 possible, but isn’t ruled out in this article. The grid-based argument used in our upper bound doesn’t seem to align with a non-orthogonal setting.

References

[1] Ramón Alvarez-Valdés, Francisco Parreño, and José Manuel Tamarit. A branch-and-cut algorithm for the pallet loading problem. Computers & Operations Research, 32(11):3007–3029, 2005. doi:10.1016/j.cor.2004.04.010.
[2] Ramón Alvarez-Valdés, Francisco Parreño, and José Manuel Tamarit. A tabu search algorithm for the pallet loading problem. Or Spectrum, 27(1):43–61, 2005. doi:10.1007/s00291-004-0183-5.
[3] Frank W. Barnes. Packing the maximum number of m × n tiles in a large p × q rectangle. Discret. Math., 26(2):93–100, 1979. doi:10.1016/0012-365X(79)90115-8.
[4] E. G. Birgin, R. D. Lobato, and R. Morabito. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. The Journal of the Operational Research Society, 61(2):306–320, 2010. doi:10.1057/jors.2008.141.
[5] ETH Zurich. Euler: High-performance computing cluster, 2024. Scientific IT Services, ETH Zurich. URL: https://scicomp.ethz.ch/wiki/Euler.
[6] International Organization for Standardization. ISO 216:2007 – writing paper and certain classes of printed matter – trimmed sizes – a and b series, and indication of machine direction, 2007.
[7] Noel Friedrich. Fun Orthonogal Rectangle Packing. https://noel-friedrich.de/forp, 2025. [Accessed 16-12-2025].
[8] Noel Friedrich. Gallery of papel. https://noel-friedrich.de/papel, 2025. [Accessed 03-01-2026].
[9] Noel Friedrich. Github repository containing material and code relating to the project. https://github.com/noel-friedrich/paper-packing, 2025. [Accessed 03-01-2026].
[10] Noel Friedrich. A4 paper is annoying (I have proof), 2026. YouTube video explaining core concepts from this paper. URL: https://www.youtube.com/watch?v=zDKBCIMkDbw.
[11] Deutsches Institut für Normung. DIN 476: Papierformate, 1976.
[12] M. Helbig and W. Hennig. DIN-Format A 4: e. Erfolgssystem in Gefahr. Beuth-Kommentare. Beuth, 1988. URL: https://books.google.ch/books?id=Eo9tAAAACAAJ.
[13] Heinz Isermann. Obere Schranken für die Lösung des zweidimensionalen Packproblems auf der Basis struktureller Identitäten, pages 341–348. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. doi:10.1007/978-3-642-76537-7_22.
[14] Markus Kuhn. International standard paper sizes, 2025. Created 1996-10-29; last modified 2025-12-08. URL: https://www.cl.cam.ac.uk/˜mgk25/iso-paper.html.
[15] Adam N. Letchford and André Renato Sales Amaral. Analysis of upper bounds for the pallet loading problem. Eur. J. Oper. Res., 132(3):582–593, 2001. doi:10.1016/S0377-2217(00)00163-6.
[16] Gustavo H. A. Martins and Robert F. Dell. The minimum size instance of a pallet loading problem equivalence class. Eur. J. Oper. Res., 179(1):17–26, 2007. doi:10.1016/j.ejor.2006.03.009.
[17] Neenah Paper. International paper sizes and dimensions. Paper 101 (states that A4 is the most common international letterhead size). URL: https://www.neenahpaper.com/resources/paper-101/international-sizes.
[18] Josef Nelißen. How to use structural constraints to compute an upper bound for the pallet loading problem. European Journal of Operational Research, 84(3):662–680, 1995. Cutting and Packing. doi:10.1016/0377-2217(95)00030-T.
[19] Elsa Silva, José F Oliveira, and Gerhard Wäscher. The pallet loading problem: a review of solution methods and computational experiments. International Transactions in Operational Research, 23(1-2):147–172, 2016. doi:10.1111/itor.12099.
[20] Saúl Vargas-Osorio and Catya Zúñiga. A literature review on the pallet loading problem. Lámpsakos, pages 69–80, 2016. doi:10.21501/21454086.1790.

Appendix A Appendix

Lower Bound Part B Placement Certificate

Each line contains integers $(x_{0},y_{0},x_{1},y_{1})$ encoding the rectangle $[x_{0},x_{1}]\times[y_{0},y_{1}]$ . All rectangles have $(x_{1}-x_{0},y_{1}-y_{0})\in\{(26,37),(37,26)\}$ .

% x0 y0 x1 y178 0 115 26115 0 152 26152 0 189 26189 0 226 2678 26 115 52115 26 152 52152 26 189 52189 26 226 5278 52 115 78115 52 152 78152 52 189 78189 52 226 7878 78 115 104115 78 152 104152 78 189 104189 78 226 104189 104 226 130189 130 226 156189 156 226 182189 182 226 208189 208 226 234189 234 226 260189 260 226 286200 286 226 323200 323 226 360200 360 226 397200 397 226 434200 434 226 471200 471 226 508200 508 226 545200 545 226 582200 582 226 619200 619 226 656200 656 226 693200 693 226 730200 730 226 767200 767 226 804200 804 226 841111 104 137 141137 104 163 141163 104 189 141111 141 137 178137 141 163 178163 141 189 178111 178 137 215137 178 163 215163 178 189 215111 215 137 252137 215 163 252163 215 189 252111 252 137 289137 252 163 289163 252 189 289163 289 200 315163 315 200 341163 341 200 367163 367 200 393163 393 200 419163 419 200 445163 445 200 471174 471 200 508174 508 200 545174 545 200 582174 582 200 619174 619 200 656174 656 200 693174 693 200 730174 730 200 767174 767 200 804174 804 200 841111 289 137 326137 289 163 326111 326 137 363137 326 163 363111 363 137 400137 363 163 400111 400 137 437137 400 163 437111 437 137 474137 437 163 474137 474 174 500137 500 174 526137 526 174 552137 552 174 578137 578 174 604137 604 174 630137 630 174 656148 656 174 693148 693 174 730148 730 174 767148 767 174 804148 804 174 841111 474 137 511111 511 137 548111 548 137 585111 585 137 622111 622 137 659111 659 148 685111 685 148 711111 711 148 737111 737 148 763111 763 148 789111 789 148 815111 815 148 8410 0 26 3726 0 52 3752 0 78 370 37 26 7426 37 52 7452 37 78 740 74 26 11126 74 52 11152 74 78 1110 111 37 13737 111 74 13774 111 111 1370 137 37 16337 137 74 16374 137 111 1630 163 37 18937 163 74 18974 163 111 1890 189 37 21537 189 74 21574 189 111 2150 215 37 24137 215 74 24174 215 111 2410 241 37 26737 241 74 26774 241 111 2670 267 37 29337 267 74 29374 267 111 2930 293 37 31937 293 74 31974 293 111 3190 319 37 34537 319 74 34574 319 111 3450 345 37 37137 345 74 37174 345 111 3710 371 37 39737 371 74 39774 371 111 3970 397 37 42337 397 74 42374 397 111 4230 423 37 44937 423 74 44974 423 111 4490 449 37 47537 449 74 47574 449 111 4750 475 37 50137 475 74 50174 475 111 5010 501 37 52737 501 74 52774 501 111 5270 527 37 55337 527 74 55374 527 111 5530 553 37 57937 553 74 57974 553 111 5790 579 37 60537 579 74 60574 579 111 6050 605 37 63137 605 74 63174 605 111 6310 631 37 65737 631 74 65774 631 111 6570 657 37 68337 657 74 68374 657 111 6830 683 37 70937 683 74 70974 683 111 7090 709 37 73537 709 74 73574 709 111 7350 735 37 76137 735 74 76174 735 111 7610 761 37 78737 761 74 78774 761 111 7870 787 37 81337 787 74 81374 787 111 8130 813 37 83937 813 74 83974 813 111 839

These coordinates can be verified using the following concise python script:

⬇

import numpy as np

rects = np.loadtxt("rect_positions.txt", dtype=int)

assert rects.shape == (197, 4)

# check correct dimensions

for x0, y0, x1, y1 in rects:

assert (x1 - x0, y1 - y0) in {(26, 37), (37, 26)}

# check containment

assert rects[:, 0].min() >= 0 and rects[:, 2].max() <= 227

assert rects[:, 1].min() >= 0 and rects[:, 3].max() <= 841

# check disjointness by checking covering map

covered_map = np.zeros((227, 841))

for x0, y0, x1, y1 in rects:

covered_map[x0:x1, y0:y1] += 1

assert covered_map.max() <= 1

Table 2: ISO 216 A-series paper sizes in millimetres.

Name	Width (mm)	Height (mm)	Nominal Width (mm)	Nominal Height (mm)
A0	841	1189	840.89641525…	1189.2071150…
A1	594	841	594.60355750…	840.89641525…
A2	420	594	420.44820762…	594.60355750…
A3	297	420	297.30177875…	420.44820762…
A4	210	297	210.22410381…	297.30177875…
A5	148	210	148.65088937…	210.22410381…
A6	105	148	105.11205190…	148.65088937…
A7	74	105	74.325444687…	105.11205190…
A8	52	74	52.556025953…	74.325444687…
A9	37	52	37.162722343…	52.556025953…
A10	26	37	26.278012976…	37.162722343…

[bib.bib1] [1] Ramón Alvarez-Valdés, Francisco Parreño, and José Manuel Tamarit. A branch-and-cut algorithm for the pallet loading problem. Computers & Operations Research, 32(11):3007–3029, 2005. doi:10.1016/j.cor.2004.04.010.

[bib.bib2] [2] Ramón Alvarez-Valdés, Francisco Parreño, and José Manuel Tamarit. A tabu search algorithm for the pallet loading problem. Or Spectrum, 27(1):43–61, 2005. doi:10.1007/s00291-004-0183-5.

[bib.bib3] [3] Frank W. Barnes. Packing the maximum number of m × n tiles in a large p × q rectangle. Discret. Math., 26(2):93–100, 1979. doi:10.1016/0012-365X(79)90115-8.

[bib.bib4] [4] E. G. Birgin, R. D. Lobato, and R. Morabito. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. The Journal of the Operational Research Society, 61(2):306–320, 2010. doi:10.1057/jors.2008.141.

[bib.bib5] [5] ETH Zurich. Euler: High-performance computing cluster, 2024. Scientific IT Services, ETH Zurich. URL: https://scicomp.ethz.ch/wiki/Euler.

[bib.bib6] [6] International Organization for Standardization. ISO 216:2007 – writing paper and certain classes of printed matter – trimmed sizes – a and b series, and indication of machine direction, 2007.

[bib.bib7] [7] Noel Friedrich. Fun Orthonogal Rectangle Packing. https://noel-friedrich.de/forp, 2025. [Accessed 16-12-2025].

[bib.bib8] [8] Noel Friedrich. Gallery of papel. https://noel-friedrich.de/papel, 2025. [Accessed 03-01-2026].

[bib.bib9] [9] Noel Friedrich. Github repository containing material and code relating to the project. https://github.com/noel-friedrich/paper-packing, 2025. [Accessed 03-01-2026].

[bib.bib10] [10] Noel Friedrich. A4 paper is annoying (I have proof), 2026. YouTube video explaining core concepts from this paper. URL: https://www.youtube.com/watch?v=zDKBCIMkDbw.

[bib.bib11] [11] Deutsches Institut für Normung. DIN 476: Papierformate, 1976.

[bib.bib12] [12] M. Helbig and W. Hennig. DIN-Format A 4: e. Erfolgssystem in Gefahr. Beuth-Kommentare. Beuth, 1988. URL: https://books.google.ch/books?id=Eo9tAAAACAAJ.

[bib.bib13] [13] Heinz Isermann. Obere Schranken für die Lösung des zweidimensionalen Packproblems auf der Basis struktureller Identitäten, pages 341–348. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. doi:10.1007/978-3-642-76537-7_22.

[bib.bib14] [14] Markus Kuhn. International standard paper sizes, 2025. Created 1996-10-29; last modified 2025-12-08. URL: https://www.cl.cam.ac.uk/˜mgk25/iso-paper.html.

[bib.bib15] [15] Adam N. Letchford and André Renato Sales Amaral. Analysis of upper bounds for the pallet loading problem. Eur. J. Oper. Res., 132(3):582–593, 2001. doi:10.1016/S0377-2217(00)00163-6.

[bib.bib16] [16] Gustavo H. A. Martins and Robert F. Dell. The minimum size instance of a pallet loading problem equivalence class. Eur. J. Oper. Res., 179(1):17–26, 2007. doi:10.1016/j.ejor.2006.03.009.

[bib.bib17] [17] Neenah Paper. International paper sizes and dimensions. Paper 101 (states that A4 is the most common international letterhead size). URL: https://www.neenahpaper.com/resources/paper-101/international-sizes.

[bib.bib18] [18] Josef Nelißen. How to use structural constraints to compute an upper bound for the pallet loading problem. European Journal of Operational Research, 84(3):662–680, 1995. Cutting and Packing. doi:10.1016/0377-2217(95)00030-T.

[bib.bib19] [19] Elsa Silva, José F Oliveira, and Gerhard Wäscher. The pallet loading problem: a review of solution methods and computational experiments. International Transactions in Operational Research, 23(1-2):147–172, 2016. doi:10.1111/itor.12099.

[bib.bib20] [20] Saúl Vargas-Osorio and Catya Zúñiga. A literature review on the pallet loading problem. Lámpsakos, pages 69–80, 2016. doi:10.21501/21454086.1790.