We put pebbles on some unit squares of a $2013 \times 2013$ chessboard such that every unit square contains at most one pebble. Determine the minimum number of pebbles on the chessboard, if each $19\times 19$ square formed by unit squares contains at least $21$ pebbles.
Problem
Source: Turkey TST 2013 - Day 1 - P2
Tags: geometry, rectangle, induction, combinatorics proposed, combinatorics
20.04.2013 13:15
We can separate the square 2013*2013 into a square 1976*1976, a square 37*37 and 208 rectangle 37*19 . Not difficult to see that : -, The square 37*37 has at least 41 pebbles -, A rectangle 37*19 has at least 23 pebbles -, The square 1976*1976 has at least $104^2.21$ pebbles So, we have at least 231961 pebbles.
20.04.2013 19:23
Is that bound achievable? Anyway, I don't think they all are "not difficult to see".
23.04.2013 17:22
Sorry, this bound is right. But i can't construct a table sastifying. The answer is larger.
23.04.2013 17:46
Well, I request you to provide how you obtain the bound (specifically, how you prove that a $37 \times 37$ square has at least $41$ pebbles, etc).
26.04.2013 19:29
You can consider two square 19.19 of two corners. They have exactly one common square 1.1, so we need at least 21+21-1=41
28.04.2013 18:22
Sorry for my mistake. The answer is 2013.105+2.106.105 We can construct this: we put pebbles on all the column 19, 38, ... ,1995 After that, on each row 19,38,...,1995, we put 2.106 pebbles on the positions: 19k+1,2 We will separate the square 2013.2013 into squares 19.19, some of them have exactly common squre 1.1. Because of my bad English, I can't describe that so I will give you an example with 56.56: We consider 6 squares with top left corn at (1,1) (19,19) (1,39) (39,1) (39,20) (20,39)
10.05.2013 06:04
Hello guys, answer is N=233625; too easy ... We define - a $n\times n$ grid as the set of the unit squares with center $(i,j), \;1\le i,j \le n$; - a “funny grid” such that each $19 \times 19$ square contains at least $21$ pebbles. - a pebble as a kind of little rock; we could use "peanut" instead ... ... We show: This $N$ is minimal 1) We show by induction that “a funny $(19n+18) \times (19n+18)$ grid contains at least $ f(n)=n(21n+20)$ pebbles” - for n=1 : a funny $37 \times 37$ grid contains two $19 \times 19$ squares, they share a unit square; hence they contains at least $21+21-1=41 =f(1)$ pebbles. - suppose it true for $n$ : consider $G$: a funny $(19n+37) \times (19n+37)$ grid $1\le i,j \le 19n+37$; it contains: - a funny grid $G_0$: $1\le i,j \le 19n+18$, with at least $f(n)$ pebbles by hypothesis, - $n+1$ squares $S(q), \; 0\le q \le n$, each of size $19\times 19$ defined by $19n+19\le i\le 19n+37,\; 19q+1\le j\le 19q+19$; they contains at least $b=21(n+1)$ pebbles, - $n+1$ squares $S'(q), \; 0\le q\le n$, each of size $19\times 19$ defined by $19n+19\le j \le 19n+37, \; 19q+1 \le i \le 19q+19$; they contains at least $c=21(n+1)$ pebbles, $S(n)$ and $S'(n)$ are the only squares to share a unit square $(19n+19,19n+19)$; the others being pairwise disjoints. In conclusion $G$ contains at least $f(n)+b+c-1= f(n+1)$ pebbles; done. 2) Here with $n= 105$, a funny $2013 \times 2013$ grid contains at least $f(105)=233625$ pebbles. This $N$ is possible Works by putting a pebble only on $(i,j)$ with $1 \le i \le 2013$ and $j=19k, \; 1 \le k \le 105$ and $i=19m, \; 1\le m\le 105, \; j=19n+18, \; 0\le n\le 105$ and $i=19m, \; 1\le m\le 105, \; j=19n+17, \; 0\le n\le 105$. The repetitive pattern readily shows that any $19\times 19$ square contains $21$ pebbles; making this grid funny (make a drawing); it contains $105$ lines of $2013$ pebbles plus $105\times 106$ blocks of $2$, -> that is $233625$ pebbles; which completes the job ... And now ? now the issue IS -> I'm sure this can be solved in a simpler way (without induction ?) can you help me ? ... that’s all folks !…