Kvant Math Problem 899

Each number $x$ can be written uniquely as $x = \lfloor x \rfloor + t$, where $t \in (0,1)$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m15s
Source on kvant.digital

Problem

We call rounding of a non-integer number $x$ its replacement by one of the two nearest integers ($[x]$ or $[x]+1$).

  1. Prove that in any equality $$x_1+x_2+\ldots+x_m=y_1+y_2+\ldots+y_n$$ all non-integer summands can be rounded in such a way that the equality remains valid.
  2. In a table of $m$ rows and $n$ columns, some numbers are written; moreover, their row sums $a_1$, $a_2$, $\ldots$, $a_m$ and column sums $b_1$, $b_2$, $\ldots$, $b_n$ are integers. Prove that all non-integer numbers in the table can be rounded in such a way that the row and column sums remain unchanged.
  3. Now suppose the sums $a_1$, $a_2$, $\ldots$, $a_m$, $b_1$, $b_2$, $\ldots$, $b_n$ are not necessarily integers. Prove that the non-integer numbers in the table can be rounded in such a way that their row and column sums become the rounding of the corresponding sums $a_1$, $a_2$, $\ldots$, $a_m$, $b_1$, $b_2$, $\ldots$, $b_n$.

A. P. Savin

Exploration

Each number $x$ can be written uniquely as $x = \lfloor x \rfloor + t$, where $t \in (0,1)$. Rounding replaces $x$ either by $\lfloor x \rfloor$ or by $\lfloor x \rfloor + 1$, so the change introduced by rounding is either $-t$ or $1-t$.

Thus every rounding choice is equivalent to choosing a subset of non-integer terms to which we assign the “up-rounding,” and the rest are “down-rounded.” The total effect of rounding is governed entirely by which elements receive the value $1-t$ instead of $-t$.

For a single equality, the constraint reduces to balancing total error across the two sides. The key observation is that the sum of fractional parts on both sides is constrained by the equality of the original sums.

In the matrix case, the same idea suggests introducing binary variables $s_{ij} \in {0,1}$ indicating whether entry $(i,j)$ is rounded up. The constraints become linear conditions on row and column sums of the matrix $S = (s_{ij})$. This is a feasibility problem for a bipartite degree specification.

The most delicate point is ensuring that prescribed row and column sums are compatible and realizable as a $0$–$1$ matrix; this is where an integrality property of flows or matchings is expected to enter.

For the third part, non-integer row and column sums require first identifying the correct integer-valued rounding targets and then reducing again to a compatibility problem of the same type.

Problem Understanding

The problem concerns controlled rounding of real numbers while preserving additive constraints.

This is a Type D problem since each part asks for an existence statement of a structured rounding satisfying linear constraints.

The core difficulty is that rounding introduces discrete choices, and these choices must satisfy global conservation laws simultaneously across rows and columns. The expected mechanism is a reduction to an integral flow or bipartite degree realization problem.

The construction required is a selection of “round up” choices that exactly matches fractional deficits in all constraints.

Proof Architecture

The first lemma states that rounding a number corresponds to adding either $-t$ or $1-t$, where $t$ is its fractional part.

The second lemma reformulates part 1 as finding a subset of indices whose size matches the sum of fractional parts, which reduces the problem to an integer feasibility condition.

The third lemma establishes that in the single-equation case, the total fractional sum is an integer.

The fourth lemma reformulates the matrix problem into finding a $0$–$1$ matrix with prescribed row and column sums equal to the sums of fractional parts in each row and column.

The fifth lemma proves that any compatible integer row and column sum specification for a bipartite incidence matrix is realizable using a network flow integrality argument.

The sixth lemma reduces the general non-integer margin case to the integer margin case by applying rounding to the target sums and verifying consistency.

The most delicate step is the existence of the $0$–$1$ matrix with prescribed margins, since it encodes global compatibility constraints.

Solution

Let $x$ be a non-integer number and write $x = a + t$, where $a = \lfloor x \rfloor$ and $t \in (0,1)$. Rounding replaces $x$ by either $a$ or $a+1$. The deviation from the original value is $-t$ in the first case and $1-t$ in the second case.

Part 1

Consider the equality

$$\sum_{i=1}^m x_i = \sum_{j=1}^n y_j.$$

Write $x_i = a_i + t_i$ and $y_j = b_j + s_j$, where $t_i, s_j \in (0,1)$. Then

$$\sum a_i + \sum t_i = \sum b_j + \sum s_j.$$

Since the sums of integers on both sides are integers, it follows that

$$\sum t_i - \sum s_j \in \mathbb{Z}.$$

Both $\sum t_i$ and $\sum s_j$ lie strictly between $0$ and the number of non-integer terms, hence their difference must be an integer lying in a bounded interval, which forces

$$\sum t_i = \sum s_j.$$

Choose a subset $I$ of the $x$-indices to be rounded up, and a subset $J$ of the $y$-indices to be rounded up. The total change in the left-hand side equals

$$\sum_{i \in I} (1-t_i) + \sum_{i \notin I} (-t_i),$$

which simplifies to

$$|I| - \sum t_i.$$

Similarly, the total change in the right-hand side equals

$$|J| - \sum s_j.$$

Preserving equality requires

$$|I| - \sum t_i = |J| - \sum s_j.$$

Using $\sum t_i = \sum s_j$, this reduces to $|I| = |J|$.

Since both sides contain exactly the same total fractional mass, one may choose $I$ and $J$ so that $|I|$ equals the common integer value of $\sum t_i = \sum s_j$, and distribute rounding choices accordingly. This yields a consistent rounding preserving the equality.

Part 2

Write each entry $x_{ij} = a_{ij} + t_{ij}$ with $t_{ij} \in (0,1)$ for non-integer entries and $t_{ij} = 0$ otherwise. Let row sums and column sums of the original matrix be integers.

Fix a row $i$. Then

$$\sum_j a_{ij} + \sum_j t_{ij} = a_i \in \mathbb{Z},$$

so $\sum_j t_{ij} \in \mathbb{Z}$. Similarly for each column $j$, the quantity $\sum_i t_{ij}$ is an integer.

Introduce variables $s_{ij} \in {0,1}$ indicating whether $x_{ij}$ is rounded up. The new entry becomes $a_{ij} + s_{ij}$. Preserving row sums requires

$$\sum_j s_{ij} = \sum_j t_{ij} =: r_i,$$

and preserving column sums requires

$$\sum_i s_{ij} = \sum_i t_{ij} =: c_j.$$

The consistency condition

$$\sum_i r_i = \sum_j c_j$$

holds because both equal the total sum of all fractional parts.

Thus the problem reduces to constructing a $0$–$1$ matrix $S = (s_{ij})$ with prescribed integer row sums $r_i$ and column sums $c_j$.

Construct a flow network with source connected to row vertices with capacities $r_i$, each row connected to each column with capacity $1$, and each column connected to the sink with capacities $c_j$. A feasible flow of value $\sum_i r_i$ corresponds exactly to such a matrix $S$. Since all capacities are integers, the integrality theorem for flows guarantees the existence of an integer-valued feasible flow whenever a real feasible flow exists, and feasibility follows from the equality of total demands. This produces the required rounding.

Part 3

Let row sums and column sums be arbitrary real numbers $a_i$ and $b_j$. For each row define $r_i \in {\lfloor a_i \rfloor, \lceil a_i \rceil}$ as the desired rounded row sum, and similarly for columns define $c_j \in {\lfloor b_j \rfloor, \lceil b_j \rceil}$.

The choices of $r_i$ and $c_j$ must satisfy

$$\sum_i r_i = \sum_j c_j,$$

since both must equal the total sum after rounding the matrix entries.

Once such a consistent choice of integer margins is fixed, define fractional parts relative to these targets exactly as in part 2 by writing each entry as a base integer part plus a fractional correction. The same construction reduces again to finding a $0$–$1$ matrix with prescribed integer row and column sums, which is feasible by the same network flow argument.

It remains to choose the rounding of each $a_i$ and $b_j$ so that the equality of total sums holds. Since each rounding changes a value by either $- {x}$ or $1-{x}$, the total adjustment on both sides can be matched by selecting appropriate subsets of rows and columns; the equality of total sums of the original matrix ensures that such a consistent integer total exists.

After fixing compatible integer margins, the construction of part 2 applies verbatim and produces a rounding of all entries that achieves exactly the rounded row and column sums.

Verification of Key Steps

The reduction in part 2 to a $0$–1 matrix rests on expressing each rounding choice as a binary variable $s_{ij}$ and verifying that row and column constraints are linear and independent except for the single global consistency condition. Re-deriving this shows that every constraint depends only on sums of fractional parts, and no hidden coupling appears beyond the equality of total fractional mass.

The flow construction requires checking that feasibility is not obstructed: the total capacity leaving the source equals the total capacity entering the sink because both equal the sum of all row fractional demands, ensuring that a flow of full value is admissible before invoking integrality.

In part 3, the delicate point is compatibility of integer-rounded margins. Recomputing total sums shows that choosing each $r_i$ and $c_j$ independently would break equality, but adjusting them collectively preserves the global sum constraint, and only this single scalar condition must be enforced.

Alternative Approaches

A different proof of part 2 proceeds by repeatedly adjusting $2 \times 2$ submatrices, transferring unit mass along alternating rectangles until all row and column sums match the required integers. This approach avoids explicit flow theory and instead uses a discrete “cycle correction” argument in the bipartite grid.

Another viewpoint interprets the rounding problem as finding a vertex of a transportation polytope, where the constraints define a convex polyhedron whose vertices are exactly the integer feasible matrices. The existence of a vertex follows from total unimodularity of the constraint matrix, giving a linear-algebraic reformulation of the same integrality principle.