Andre's (Tudor Vianu School) started of by giving his thoughts on the problem. Many thanks for this Andre - I think it is an excellent attempt to unpick what is happening.

For a 2 x 2
Cube

First, I analysed a 2x2x2 cube. After dipping it into the pot
of yellow paint, each cube has three faces painted yellow and three
faces painted red (the original colour). So, the other three faces
of the cube remain red. Reversing each cube (so that each exterior
vertex goes into the centre of the big cube) all the red faces
remain at the exterior. After dipping the cube into the green pot,
the rest of the face that remained red are now coloured green. So,
it is sufficient to use two colours.

Side of cube | Small cubes | Faces (total) | Faces (exterior) | Colours |

2 | 8 | 6 x 8 = 48 | 6 x 4 = 24 | 2 |

3 | 27 | 6x 27 = 162 | 6 x 9 = 54 | 3 |

4 | 64 | 6 x 64 = 384 | 6 x 16 = 96 | 4 |

n | n x n x n | 6 x n x n x n | 6 x n x n | n |

Now, I analysed the situation with 3x3x3 cubes. I created 27
cubes from paper in order to analyse the situation experimentally.
I see that in order to make possible to colour all the faces using
3 colours, each face must be coloured only once. After trying
several times I observed that this is impossible, because the
number of cubes with different numbers of coloured faces is very
different:

After the first dipping:

- there are 8 cubes with three coloured faces (vertices)
- there are 12 cubes with 2 coloured faces (centres of edges)
- there are 6 cubes with 1 coloured 1 face (centres of faces)
- there is 1 cube with no coloured faces (centre of big cube)

I used in my solutions the following considerations:-

- the cube from the centre must go into one vertex, to maximise its coloured faces in the following step
- one cube from one vertex must go into the centre of the big cube
- the other cubes from the vertices must go into the centres of the faces (6), and one in a centre of the edges
- the cubes from the centres of the faces must go into the vertices

The third of these assumptions was
incorrect. Someone else then completed the solution:

For an n x n x n cube (if n is 6 or greater, or is 4), can be coloured as follows:

- We start of with 8 corner pieces, 12(n-2) edge pieces, 6(n-2)^2 centres, and (n-3)^3 middles
- 4n blocks are looped around spending 2 dips in the corners, and (n-2) dips in the middles. This leaves 12(n-2) edges, 6(n-2)^2 centres and n(n-2)(n-4) middles.
- 6n(n-2) gaps are kept for blocks spending 2 times at the edge, 2 times at the centre, and (n-4) times in the middle

The 'missing' case is n=5. Here instead of the second point we would use 52 of the centre slots and 13 of the middle slots to move around a total of 65 cubes in to cover them in the five dips. We would then use 2 of the edge slots, two of the centre slots, and one middle to colour 5 more blocks in the 5 dips. Finally we would use the 21 edge slots and 14 middle slots to cover a total of 35 blocks using a total of 5 dips (so each block spends two 3 times at an edge and 2 times in the middle).

So an n*n*n block can be covered in n dips of paint as expected.