Nice one! I've solved only part (a) till now though Let the bottom left corner be the origin and let $(i,j)$ be the cell in the ith column and jth row. (The bottom left square is $(1,1)$) I claim that the answer is $7$. A construction is simple, color $(2,4), (3,2), (3,6), (4,4), (5,2), (5,6), (6,4)$, which works. Now, assume FTSOC that it is possible to color only $6$ squares and still not find a Greek cross. (If it can be done with lesser, wont matter if any more are colored) Observe that if there is a square that has been colored on the boundary, then moving it one square to the inner 5x5 square will not spoil anything. So now, assume that all the $6$ squares are in the inner 5x5 square. Also, in each of the four triplets of "corner squares" in the 5x5 square, at least one must be colored or there would be a Greek cross (For example, among (2,2), (3,2), (2,3), one must be colored).Now, consider $2$ cases. Case 1 : There is a row or column with no square colored If there is such a column, just rotate the figure so that its now a row. Now, consider the triplets of consecutive squares on the empty row. For each triplet, since there cant be a Greek cross, out of the pair of squares above and below the middle square of the triplet, one of them must be colored. Now, at least $5$ squares must be used up like this, and we can easily see that $1$ more square will not be able to cover the remaining squares and so this is not possible. Case 2 : Every row and column has at least one colored square Since all colored squares are in the inner 5x5 square, we see that $4$ of the rows/columns must have one colored square and one row must have two if them. Now, consider 2 subcases Case 2.a : One of the corners of the 5x5 square is colored WLOG let the colored square be $(2,2)$ and assume that the row doesn't have any other colored cell (If it does, rotate the table). This means that $(6,3)$ must be colored and no other in that row can be colored. But observe that this means that $(5,3)$ and $(4,3)$ must be colored to prevent Greek squares, but this is a contradiction since no row can have more than $2$ colored squares. Case 2.b : None of the corners of the 5x5 square are colored Since one of the three "corner squares" on each corner must be covered, WLOG let $(3,2)$ be colored and let there be no colored square in that row and so $(6,3)$ must be colored. Observe that $(5,3)$ must be colored to prevent a Greek square and so now all the other rows have at most one colored square. Now, just keep doing this and it is easy to find a contradiction. Since we have exhausted all possible cases, we must conclude that a minimum of $7$ squares need to be colored so that an entirely uncolored Greek cross cannot be found on the table

Yay I have a crazy construction for part (b)

Edit: I just realized that all this crazy stuff wasnt needed, all u need to do is put a $-5$ in each colored square and $1$ in all the other squares. Then, in each Greek square, the sum is $-1$ but the overall sum of the board is $3$. I have no idea why I had to do all this nonsense for that.

L567 wrote: all u need to do is put a $-5$ in each colored square and $1$ in all the other squares. Then, in each Greek square, the sum is $-1$ but the overall sum of the board is $3$. Yeah, you're right! To be exact, the sum in each Greek square would be less than or equal to $-1$. [asy][asy] size(6.5cm); pathpen=black; pair[] P(real[] A, real[] B) {pair[] X; for(real i : A) {for(real j : B) {X.push((i,j));}} return X;} void R(string s, real[] A, real[] B) {for(pair x : P(A, B)) {clip(CR(x, 0.4)^^box((-1,-1), (8,8)), evenodd); MP(s, x, (0,0));}} void S(string s, real[] A, real[] B) {for(pair x : P(A, B)) {clip(CR(x, 0.4)^^box((-1,-1), (8,8)), evenodd); filldraw(box(x-(.5,.5), x+(.5,.5)), black); MP(s, x, (0,0), white);}} for(int i=2; i<6; ++i) {DPA((0,i)--(7,i)^^(i,0)--(i,7));} DPA(box((0,1), (7,6))^^box((1,0), (6,7))); real[] X={0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5}, Y={0.5, 6.5}, X1={2.5, 4.5}, Y1={1.5, 5.5}, X2={1.5, 3.5, 5.5}, Y2={3.5}; R("1", X, X); R("", Y, Y); S("-5", X1, Y1); S("-5", X2, Y2); [/asy][/asy]

I read the attached solution in an e-book from Internet. All parts are ok but I really don't understand the claim highlighted. Can anybody help to clarify it for me. I will also take reference to the solution of L567