logoChat01.ai

Problem Consider a 2025 x 2025 grid of unit square...

Tạo vào: 18 tháng 9, 2026

Trả lời bằng GPT-5.6 Thinking bởi Chat01

Câu hỏi

Problem
Consider a 2025 x 2025 grid of unit squares. Matilda wishes to place on the grid some rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.

Determine the minimum number of tiles Matilda needs to place so that each row and each column of the grid has exactly one unit square that is not covered by any tile.

Python

python
import scipy, scipy.optimize as opt, itertools, numpy as np, math, collections
print(scipy.__version__, hasattr(opt,'milp'))

Python

python
from scipy.optimize import milp, LinearConstraint, Bounds
def min_rect_for_perm(p):
    n=len(p)
    holes={(r,p[r]) for r in range(n)}
    cells=[(r,c) for r in range(n) for c in range(n) if (r,c) not in holes]
    idx={x:i for i,x in enumerate(cells)}
    rects=[]
    covers=[]
    for r1 in range(n):
      for r2 in range(r1,n):
       for c1 in range(n):
        for c2 in range(c1,n):
         rc=[(r,c) for r in range(r1,r2+1) for c in range(c1,c2+1)]
         if any(x in holes for x in rc): continue
         rects.append((r1,r2,c1,c2))
         covers.append([idx[x] for x in rc])
    A=np.zeros((len(cells),len(rects)))
    for j, inds in enumerate(covers):
        A[inds,j]=1
    res=milp(np.ones(len(rects)), integrality=np.ones(len(rects)),
             bounds=Bounds(0,1), constraints=LinearConstraint(A,1,1),
             options={"time_limit": 10})
    return round(res.fun), rects, res.x
for n in range(2,6):
    best=999; bp=None
    vals=collections.Counter()
    for p in itertools.permutations(range(n)):
        v,_,_=min_rect_for_perm(p)
        vals[v]+=1
        if v<best: best=v; bp=p
    print(n,best,bp,vals)

Python

python
# sample all 720 n6 maybe feasible but lots MILP; try promising "bit-reversal" / step 2 cyclic etc.
cands=[
(0,2,4,1,3,5),
(1,3,5,0,2,4),
(1,3,5,0,2,4),
(2,5,1,4,0,3),
(1,4,0,3,5,2),
]
for p in cands:
    v, rects, x=min_rect_for_perm(p)
    print(p,v)

Python

python
for n in range(2,9):
    p=tuple(list(range(0,n,2))+list(range(1,n,2)))
    v,_,_=min_rect_for_perm(p)
    print(n,p,v,'formula',n+math.ceil(math.log2(n))-1)

Python

python
p=(1,3,0,2)
v, rects, x=min_rect_for_perm(p)
sel=[r for r,a in zip(rects,x) if a>.5]
v,sel


(5, [(0, 0, 2, 3), (0, 1, 0, 0), (1, 2, 1, 2), (2, 3, 3, 3), (3, 3, 0, 1)])

Python

python
p=(1,3,5,0,2,4)
v, rects, x=min_rect_for_perm(p)
sel=[r for r,a in zip(rects,x) if a>.5]
v,sel


(8,
 [(0, 0, 2, 3),
  (0, 1, 4, 5),
  (0, 2, 0, 0),
  (1, 3, 1, 2),
  (2, 4, 3, 4),
  (3, 5, 5, 5),
  (4, 5, 0, 1),
  (5, 5, 2, 3)])

Python

python
for n in range(2,11):
    p=tuple(list(range(1,n,2))+list(range(0,n,2)))
    v,_,_=min_rect_for_perm(p)
    print(n,p,v, 'n+ceil(log2n)-1', n+math.ceil(math.log2(n))-1)

Python

python
import random, time
def sample_best(n, samples=200):
    best=999; bp=None
    t=time.time()
    for _ in range(samples):
        p=list(range(n)); random.shuffle(p); p=tuple(p)
        v,_,_=min_rect_for_perm(p)
        if v<best:
            best=v; bp=p
            print("new",n,best,bp)
            if best<=n+math.ceil(math.log2(n))-1: break
    return best,bp,time.time()-t
sample_best(7,200)


(10, (3, 6, 2, 5, 1, 4, 0), 1.1235244274139404)

Python

python
def hole_tile_adjacency(n,p,sel):
    # map cell to tile
    m={}
    for ti,(r1,r2,c1,c2) in enumerate(sel):
        for r in range(r1,r2+1):
            for c in range(c1,c2+1): m[(r,c)]=ti
    adj=[]
    for r,c in enumerate(p):
        s=[]
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            rr,cc=r+dr,c+dc
            if 0<=rr<n and 0<=cc<n: s.append(m[(rr,cc)])
        adj.append(s)
    return adj
for n,p in [(4,(1,3,0,2)),(6,(1,3,5,0,2,4))]:
    v,rs,x=min_rect_for_perm(p); sel=[r for r,a in zip(rs,x) if a>.5]
    ad=hole_tile_adjacency(n,p,sel)
    print(n,ad, [sum(i in a for a

Python

python
for n in [5,7,8,10]:
    p=tuple(list(range(1,n,2))+list(range(0,n,2)))
    v,rs,x=min_rect_for_perm(p); sel=[r for r,a in zip(rs,x) if a>.5]
    deg=[0]*v
    ad=hole_tile_adjacency(n,p,sel)
    for a in ad:
        for i in a: deg[i]+=1
    print(n,v,collections.Counter(deg),sum(deg))

Python

python
def partition_segments(n,p,sel):
    # label grid cells holes -1 or tile idx
    lab=np.empty((n,n),dtype=int)
    lab.fill(-999)
    for r,c in enumerate(p): lab[r,c]=-1
    for ti,(r1,r2,c1,c2) in enumerate(sel):
        lab[r1:r2+1,c1:c2+1]=ti
    # internal boundary unit edges horizontal (between rows r-1,r at y=r), vertical x=c
    # maximal straight segments stop at T/cross? Actually maximal collinear connected boundary regardless junction
    hs=[] # y, x intervals units where labels differ
    for y in range(1,n):
        xs=[x for x in range(n) if lab[y-1,x]!=lab[y,x]]
        # contiguous runs
        for _,grp in itertools.groupby(enumerate(xs),lambda z:z[1]-z[0]):
            vals=[z[1] for z in grp]
            hs.append((y,min(vals),max(vals)+1))
    vs=[]
    for x in range(1,n):
        ys=[y for y in range(n) if lab[y,x-1]!=lab[y,x]]
        for _,grp in itertools.groupby(enumerate(ys),lambda z:z[1]-z[0]):
            vals=[z[1] for z in grp]
            vs.append((x,min(vals),max(vals)+1))
    # But a straight boundary can pass through crossing? yes remains one segment. Runs works.
    # count red sides lying on each seg
    red_h=[]
    for seg in hs:
        y,x1,x2=seg
        cnt=0; holes=[]
        for r,c in enumerate(p):
            if y==r and x1<=c and c+1<=x2: cnt+=1;holes.append(r)
            if y==r+1 and x1<=c and c+1<=x2: cnt+=1;holes.append(r)
        red_h.append((seg,cnt,holes))
    red_v=[]
    for seg in vs:
        x,y1,y2=seg
        cnt=0;holes=[]
        for r,c in enumerate(p):
            if x==c and y1<=r and r+1<=y2: cnt+=1;holes.append(r)
            if x==c+1 and y1<=r and r+1<=y2: cnt+=1;holes.append(r)
        red_v.append((seg,cnt,holes))
    # crossings proper between internal maximal segments
    C=0
    for y,x1,x2 in hs:
        for x,y1,y2 in vs:
            if x1 < x < x2 and y1 < y < y2: C+=1
    return hs,vs,red_h,red_v,C
for n,p in [(6,(1,3,5,0,2,4)),(4,(1,3,0,2))]:
    v,rs,x=min_rect_for_perm(p);sel=[r for r,a in zip(rs,x) if a>.5]
    hs,vs,rh,rv,C=partition_segments(n,p,sel)
    P=sum(cnt==2 for _,cnt,_ in rh+rv)
    print(n,v,len(hs)+len(vs),P,C, [(s,c,h) for s,c,h in rh+rv if c==2])

Python

python
def paired_graph(n,p,sel):
    hs,vs,rh,rv,C=partition_segments(n,p,sel)
    edges=[]
    for typ,arr in [('H',rh),('V',rv)]:
        for seg,cnt,holes in arr:
            if cnt==2: edges.append((holes[0],holes[1],typ,seg))
    deg=collections.Counter()
    for a,b,*_ in edges:
        deg[a]+=1;deg[b]+=1
    return edges,deg,C
n=6;p=(1,3,5,0,2,4)
v,rs,x=min_rect_for_perm(p);sel=[r for r,a in zip(rs,x) if a>.5]
edges,deg,C=paired_graph(n,p,sel)
edges,deg


([(0, 1, 'H', (1, 1, 4)),
  (1, 2, 'H', (2, 3, 6)),
  (3, 4, 'H', (4, 0, 3)),
  (4, 5, 'H', (5, 2, 5)),
  (0, 3, 'V', (1, 0, 4)),
  (1, 4, 'V', (3, 1, 5)),
  (2, 5, 'V', (5, 2, 6))],
 Counter({1: 3, 4: 3, 0: 2, 2: 2, 3: 2, 5: 2}))

Python

python
for n in [2,3,4,5]:
    p=tuple(range(n))
    v,rs,x=min_rect_for_perm(p);sel=[r for r,a in zip(rs,x) if a>.5]
    hs,vs,rh,rv,C=partition_segments(n,p,sel)
    P=sum(cnt==2 for _,cnt,_ in rh+rv)
    print(n,v,len(hs)+len(vs),P,C,3*n-3-P+C)

Python

python
def cross_matrix(p):
    n=len(p); q=[0]*n
    for i,c in enumerate(p): q[c]=i
    M=np.zeros((n-1,n-1),dtype=int)
    for i in range(n-1):
        a,b=p[i],p[i+1]
        lo,hi=sorted((a,b))
        for j in range(lo,hi): # j boundaries crossed
            r1,r2=q[j],q[j+1]
            if min(r1,r2)<=i<max(r1,r2):
                M[i,j]=1
    return M
def max_P_minus_C(p):
    n=len(p); M=cross_matrix(p)
    m=2*(n-1)
    best=-1; maskbest=0
    # for n<=6 brute
    for mask in range(1<<m):
        H=[i for i in range(n-1) if mask>>i&1]
        V=[j for j in range(n-1) if mask>>(n-1+j)&1]
        P=len(H)+len(V)
        C=sum(M[i,j] for i in H for j in V)
        val=P-C
        if val>best: best=val;maskbest=mask
    return best,M,maskbest
for n in range(2,6):
    vals=collections.Counter()
    mx=-1
    for p in itertools.permutations(range(n)):
        b,_,_=max_P_minus_C(p)
        vals[b]+=1;mx=max(mx,b)
    print(n,vals,'bound',math.floor(1.5*n)-2)

Python

python
def gf2_rank(A):
    A=A.copy()%2
    m,n=A.shape; r=0
    for c in range(n):
        piv=next((i for i in range(r,m) if A[i,c]),None)
        if piv is None: continue
        A[[r,piv]]=A[[piv,r]]
        for i in range(m):
            if i!=r and A[i,c]: A[i]^=A[r]
        r+=1
    return r
for n in range(2,8):
    ranks=collections.Counter()
    for p in itertools.permutations(range(n)):
        ranks[gf2_rank(cross_matrix(p))]+=1
    print(n,ranks)
    if n>=7: break

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Suy nghĩ

undefined

Python

python
def construct_holes_central(k):
    N=k*k
    holes=set()
    for u in range(1,k+1):
        for v in range(1,k+1):
            r=(u-1)*k+v
            c=(v-1)*k+(k+1-u)
            holes.add((r,c))
    central=[]
    for u in range(1,k):
        for v in range(1,k):
            rA=(u-1)*k+v
            cA=(v-1)*k+(k+1-u)
            # rows rA+1..rA+k ; cols cA..cA+k-1
            central.append((rA+1,rA+k,cA,cA+k-1))
    cov=set()
    for r1,r2,c1,c2 in central:
        for r in range(r1,r2+1):
            for c in range(c1,c2+1):
                assert (r,c) not in holes
                assert (r,c) not in cov
                cov.add((r,c))
    rem={(r,c) for r in range(1,N+1) for c in range(1,N+1)}-holes-cov
    return holes,central,rem
for k in [2,3,4,5]:
    h,cen,rem=construct_holes_central(k)
    print(k, len(cen),len(rem), "target edge tile count",4*(k-1))

Python

python
from collections import deque
def comps(cells):
    cells=set(cells); out=[]
    while cells:
        s=cells.pop(); q=[s]; comp={s}
        while q:
            r,c=q.pop()
            for d in [(-1,0),(1,0),(0,-1),(0,1)]:
                t=(r+d[0],c+d[1])
                if t in cells:
                    cells.remove(t); comp.add(t); q.append(t)
        out.append(comp)
    return out
for k in [3,4,5]:
    h,cen,rem=construct_holes_central(k)
    cs=comps(rem)
    print('k',k,'components',len(cs),[len(x) for x in cs][:20])
    # bounds and rectangle check
    for comp in sorted(cs,key=lambda x:min(x))[:]:
        rs=[r for r,c in comp]; cs2=[c for r,c in comp]
        bbox=(min(rs),max(rs),min(cs2),max(cs2))
        rect=(len(comp)==(bbox[1]-bbox[0]+1)*(bbox[3]-bbox[2]+1))
        print(bbox,len(comp),rect)
    print()

Python

python
k=5
h,cen,rem=construct_holes_central(k)
cs=comps(rem)
# component with cols 1..4
comp=min(cs, key=lambda comp:max(c for r,c in comp))
for r in range(1,k*k+1):
    cols=sorted(c for rr,c in comp if rr==r)
    if cols:
        print(r, (min(cols),max(cols)), len(cols))

Python

python
# print each component profiles
k=5
h,cen,rem=construct_holes_central(k)
cs=comps(rem)
for comp in cs:
    rs=[r for r,c in comp]; csx=[c for r,c in comp]
    print('bbox',min(rs),max(rs),min(csx),max(csx))
    # group identical row intervals
    groups=[]
    cur=None
    for r in range(1,k*k+1):
        cols=sorted(c for rr,c in comp if rr==r)
        iv=(min(cols),max(cols)) if cols else None
        if iv!=cur:
            groups.append((r,iv));cur=iv
    print(groups)

Python

python
def explicit_tiles(k):
    N=k*k
    holes=set()
    for u in range(1,k+1):
        for v in range(1,k+1):
            r=(u-1)*k+v
            c=(v-1)*k+(k+1-u)
            holes.add((r,c))
    tiles=[]
    # central
    for u in range(1,k):
      for v in range(1,k):
        rA=(u-1)*k+v
        cA=(v-1)*k+(k+1-u)
        tiles.append((rA+1,rA+k,cA,cA+k-1,'C'))
    # left
    for u in range(1,k):
        tiles.append(((u-1)*k+1,u*k,1,k-u,'L'))
    # right u=2..k
    for u in range(2,k+1):
        tiles.append(((u-1)*k+1,u*k,N-u+2,N,'R'))
    # top rows 1..k-1
    for r in range(1,k):
        tiles.append((r,r,r*k+1,N,'T'))
    # bottom-ish rows N-k+2..N indexed v 1..k-1
    for v in range(1,k):
        rr=N-k+1+v
        tiles.append((rr,rr,1,v*k,'B'))
    cov={}
    for idx,(r1,r2,c1,c2,t) in enumerate(tiles):
        assert r1<=r2 and c1<=c2
        for r in range(r1,r2+1):
            for c in range(c1,c2+1):
                if (r,c) in holes:
                    return False,('hole',idx,(r,c),tiles[idx])
                if (r,c) in cov:
                    return False,('overlap',idx,cov[(r,c)],(r,c),tiles[idx])
                cov[(r,c)]=idx
    allcells={(r,c) for r in range(1,N+1) for c in range(1,N+1)}
    return len(tiles)==(k-1)**2+4*(k-1) and set(cov)==allcells-holes, (len(tiles), len(cov), len(allcells-holes))
for k in range(2,8):
    print(k,explicit_tiles(k))

Suy nghĩ

Computed and validated rectangular tilings of staircase regions

Worked for 7m 30s

Trả lời

2112\boxed{2112}

The sharp construction and the standard lower-bound approach use the fact that the 20252025 uncovered squares form a permutation, together with increasing/decreasing subsequences. (Evan Chen)

1. Lower bound

Put N=2025N=2025, and call the uncovered unit squares holes. Since every row and every column contains exactly one hole, if pip_i is the column of the hole in row ii, then

p1,p2,…,pNp_1,p_2,\ldots,p_N

is a permutation of 1,…,N1,\ldots,N.

Temporarily regard the holes themselves as NN additional rectangular pieces. Thus the whole N×NN\times N board is partitioned into T+NT+N rectangles, where TT is Matilda's number of tiles.

Consider all maximal internal horizontal and vertical boundary segments of this rectangular partition. Let their numbers be H,VH,V, and let II be the number of proper crossings of a horizontal and vertical segment. A corner count gives

T+N=H+V+I+1,T+N=H+V+I+1,

and hence

T=H+V+I+1−N.(1)T=H+V+I+1-N. \tag{1}

Indeed, the four outer corners contribute 44 rectangle corners, every segment endpoint contributes two, and every crossing contributes four.

For 1≤i<N1\le i<N, look at the horizontal grid line separating rows ii and i+1i+1. The two holes in those rows both have a side on this line. Set

ui={0,if those two sides lie on the same maximal segment,1,otherwise.u_i= \begin{cases} 0,&\text{if those two sides lie on the same maximal segment},\\ 1,&\text{otherwise}. \end{cases}

Then

H≥N−1+∑i=1N−1ui.H\ge N-1+\sum_{i=1}^{N-1}u_i.

Define wjw_j analogously for the vertical line separating columns j,j+1j,j+1. Also let Xj,i=1X_{j,i}=1 when the relevant horizontal and vertical maximal segments cross at grid point (j,i)(j,i), and 00 otherwise. From (1),

T≥N−1+∑ui+∑wj+∑Xj,i.(2)T\ge N-1+\sum u_i+\sum w_j+\sum X_{j,i}. \tag{2}

This rectangulation formulation is one elementary way to make the LIS/LDS lower bound rigorous. (Tomesphere)

Now let aa be the length of a longest increasing subsequence (LIS) of pip_i, and bb the length of a longest decreasing subsequence (LDS).

Take two consecutive members pr<psp_r<p_s, r<sr<s, of a longest increasing subsequence. There can be no hole strictly inside the rectangle

r<y<s,pr<x<ps,r<y<s,\qquad p_r<x<p_s,

because such a hole could be inserted into the subsequence.

Consequently, while passing from row rr to row ss, the holes must at some point jump directly from the left side of this empty rectangle to the right side. Thus for some i∈[r,s−1]i\in[r,s-1],

pi≤pr<ps≤pi+1.(3)p_i\le p_r<p_s\le p_{i+1}. \tag{3}

Similarly, if qjq_j denotes the row occupied by the hole in column jj, then for some j∈[pr,ps−1]j\in[p_r,p_s-1],

qj≤r<s≤qj+1.(4)q_j\le r<s\le q_{j+1}. \tag{4}

At the grid point (j,i)(j,i), if ui=0u_i=0, the corresponding horizontal segment runs completely across that point; if wj=0w_j=0, the vertical segment does likewise. Hence, if both are zero, the two segments cross there. Therefore

ui+wj+Xj,i≥1.u_i+w_j+X_{j,i}\ge1.

Each of the a−1a-1 gaps of the LIS gives one such contribution. The same argument for the LDS gives another b−1b-1 contributions.

These contributions are all distinct: the LIS jumps have pi<pi+1p_i<p_{i+1}, while the LDS jumps have pi>pi+1p_i>p_{i+1}, and the analogous statement holds in the columns. Hence

∑ui+∑wj+∑Xj,i≥(a−1)+(b−1).\sum u_i+\sum w_j+\sum X_{j,i}\ge (a-1)+(b-1).

By (2),

T≥N+a+b−3.(5)T\ge N+a+b-3. \tag{5}

It remains to bound a+ba+b. For each ii, let AiA_i and BiB_i be the lengths of the longest increasing and decreasing subsequences ending at pip_i. The pairs (Ai,Bi)(A_i,B_i) are all distinct: if i<ji<j, then either pi<pjp_i<p_j, forcing Aj>AiA_j>A_i, or pi>pjp_i>p_j, forcing Bj>BiB_j>B_i. Thus there are NN distinct pairs inside an a×ba\times b array, so

ab≥N.ab\ge N.

Therefore

a+b≥2ab≥22025=90.a+b\ge2\sqrt{ab}\ge2\sqrt{2025}=90.

Putting this into (5),

T≥2025+90−3=2112.(6)T\ge2025+90-3=2112. \tag{6}

2. Construction with 21122112 tiles

Write

2025=452,2025=45^2,

and more generally set N=k2N=k^2, with k=45k=45.

Number the rows and columns 1,…,k21,\ldots,k^2. For every 1≤u,v≤k1\le u,v\le k, leave uncovered the square

((u−1)k+v,  vk+1−u).(7)\bigl((u-1)k+v,\; vk+1-u\bigr). \tag{7}

The row coordinates in (7) run through 1,…,k21,\ldots,k^2 exactly once, and so do the column coordinates. Thus there is exactly one hole in every row and column.

Between these holes one can place

(k−1)2(k-1)^2

disjoint k×kk\times k tiles; the four staircase-shaped boundary portions are each tiled by another k−1k-1 rectangles. Hence the total is

(k−1)2+4(k−1)=k2+2k−3.(k-1)^2+4(k-1) =k^2+2k-3.

This is the k2k^2 construction illustrated in the IMO solution notes. (Evan Chen)

For k=45k=45,

442+4⋅44=1936+176=2112.44^2+4\cdot44 =1936+176 =\boxed{2112}.

Thus the lower bound is attained, so the minimum number of tiles is

2112.\boxed{2112}.

Chia sẻ Q&A này