elaborando

Ho ragionato su quale potrebbe essere una formula ricorsiva per calcolare il numero di tagli, senza però riuscire a dimostrare che è il numero minimo.
Parto con una tavoletta con un solo quadratino, che richiede ovviamente zero tagli.
Posso far crescere la tavoletta 1x1 con successivi raddoppi, lungo il bordo destro e successivamente lungo il bordo inferiore. Ottengo così, via via, tavolette 2x1, 2x2, 4x2, 4x4, 8x4 e, volendo, potrei continuare.
Il numero di tagli, ad ogni passaggio, diventa uno più il doppio dei tagli del passaggio precedente (c'è da dividere due pezzi uguali a quello intero del passaggio precedente). Quindi:
- 1x1 --> 0 tagli
- 2x1 --> 1 + 2 * 0 = 1
- 2x2 --> 1 + 2 * 1 = 3
- 4x2 --> 1 + 2 * 3 = 7
- 4x4 --> 1 + 2 * 7 = 15
- 8x4 --> 1 + 2 * 15 = 31
La sequenza di divisione è allora quella di dividere in due parti ogni pezzo, fino a ridurre tutto in singoli quadratini.
Allo stesso numero di tagli si arriva anche tagliando così:
7 tagli per dividere in otto strisce
3 tagli per dividere ogni striscia in 4 quadratini
Quindi: 7 + 3 + 8 = 31