A positive integer $n$ is given. A cube $3\times3\times3$ is built from $26$ white and $1$ black cubes $1\times1\times1$ such that the black cube is in the center of $3\times3\times3$-cube. A cube $3n\times 3n\times 3n$ is formed by $n^3$ such $3\times3\times3$-cubes. What is the smallest number of white cubes which should be colored in red in such a way that every white cube will have at least one common vertex with a red one.
HIDE: thanks Thanks to the user Vlados021 for translating the problem.Problem
Source:
Tags:
stroller
05.05.2019 22:25
We say that something is covered if it is red or has a common vertex with a red square/cube.
[2D case]: We say that a $3\times 3$ square with center colored black is a well. Given $m\times n$ rectangular array of wells, $m < n$, at least $m(n+1)$ red cubes are needed to cover the well. Equality case:
010010010
040040040
000000000
010010010
040040040
000000000
010010010
040040040
010010010
4=black
1=red
0=white
Proof: The base case $m = 0$ is trivial. Suppose the statement holds for $m-1, m \in \mathbb N$. Number the rows $1,2,...,m$ from bottom to top. The key is the
Claim: Let $C$ be the leftmost two columns and $R$ the lowest two rows, then either $C$ contains $m+1$ or $R$ has $n+1$ red squares.
Proof of claim: Column, row $1$ refer to the column, row of unit squares without red squares in $C,R$ respectively while column, row $2$ refer to the others. All squares in row $1$ must be covered by squares in $R$, $n$ red squares are needed, and exactly $n$ iff the red squares in $R$ are exactly the unit squares $2,5,8,...$ in row $1$. Note that equality case cannot hold for $R,C$ simultaneously, from which the claim follows.
To complete the proof, suppose $a_{m,n}$ red squares are needed. We wish to have $a_{m,n} \ge \min\{a_{m-1,n}+n+1,a_{m,n-1}+m+1\} = m(n+1)$.
We demonstrate how to reduce to smaller cases. Suppose there are $n+1$ red squares in $R$, shift all red squares in row $3$ into row $4$ and delete rows $1,2,3$ reduces the situation to that of $m-1\times n$ array of wells. Similar reduction for the case when $m+1$ red squares are in $C$.
3D Case:
From 2D Case consider deleting the two planes with lowest $z$ coordinates, say $z = 1,2,3$ (where we arrange cubes with sides parallel to $x,y,z$ axes) and bumping all red points in the plane $z = 3$ into the plane $z = 4$ before the deletion. We prove by induction that the answer is $a_{mnk} = m\times n\times (k+1)$ where $m \le n \le k$ and $k$ is the highest $z$ coordinate among all unit squares considered.
Base cases $m=n=1\le k$ are evident. Suppose the statement holds for $(m,n,k-1)$ then the above deletion yields $a_{m,n,k} \ge a_{m,n,k-1} + mn \ge mnk + mn = mn(k+1)$ for all $k > n$. Now if $k = n$ then $a_{m,n,n} \ge a_{m,n-1,n} + n^2 = m(n-1)(n+1) + n^2 = mn(n+1)-m(n+1) + n^2 \ge mn(n+1)$ for all $m < n$. It suffices to consider the case $(n,n,n)$ and show that if this is the case then one of the groups $X:=\{x = 1\}\cup \{x=2\}$, $Y$, $Z$ defined similarly as before must have $n(n+1)$ red cubes...
The claim in 2D case carries over to 3D as well (Among any three orthogonal $n\times 1\times 1$ sticks of 3D-wells that share a 3D-well, one of them must contain $\ge n+1$ red cubes) by considering equality cases like before.
stroller
23.06.2019 23:01
Bump
Kassuno
28.07.2019 16:30
Bump
mijail
27.09.2019 03:57
Bump Bump
Belgutei
02.01.2020 07:48
Is this smallest number:n*n*n+n
JBMO2020
03.04.2020 20:04
The answer is $(n+1)n^2$
stroller
19.04.2020 23:44
bump Belgutei wrote: Is this smallest number:n*n*n+n JBMO2020 wrote: The answer is $(n+1)n^2$ see "partial progress on 3D?" part and also a complete proof for 2D in post #2
Idio-logy
26.06.2020 12:51
The answer is $n^2(n+1)$ as expected. For $x=1,2,\dots,3n$ let \[ f(x)= \begin{cases} \frac{x}{3} & \text{ if } x\equiv 0 \mod 3\\ n-\frac{x-1}{3} & \text{ if } x\equiv 1\mod 3\\ 0 & \text{ if } x\equiv 2\mod 3 \end{cases} \]For a cube with coordinate $x,y,z$ label it with $f(x)f(y)f(z)$, then the sum of all labels is equal to $n^3(n+1)^3$. For each white cube (one of whose coordinates is not 2 modulo 3), the sum of labels on the $3^3=27$ it touches is at most $n(n+1)^2$, so we need to paint at least $n^2(n+1)$ cubes red.
CANBANKAN
13.03.2021 23:30
The answer is $n^2(n+1)$. We first solve the 2d case. The answer is $n(n+1)$. The construction is placing red squares at $(3k-1,1)$ and $(3k-1,3k)$ for $k\ge 1$. To show this is optimal, let $f(n)$ be the number of squares I can label such that no two can be covered by one red square. I claim $f(n)-f(n-2)\ge 4n-2$. Indeed, consider placing red squares at $(3k,1), (1,3k), (3n, 3k), (3k, 3n)$. We've placed $4n-2$ squares and this reduces to a $3(n-2)^2$ square. Since $f(0)=0, f(1)=2$, we are done. Now, we solve the 3d case. The construction is simply the 2d construction at layers $3k+2, k\ge 0$. Labelling squares is also labelling on layers $3k+1, k\ge 0$.
Attachments:
skyboy2007
25.12.2022 17:00
(n+1)n^2