Oplossingsmethode

Aangezien iedere poster aan zijn vier hoekpunten moet worden vastgemaakt heb je voor 1 poster uiteraard 4 punaises nodig. De tweede poster kunnen we er dan naast prikken, wat nog eens 2 extra punaises kost. Maar hoe ga je dan verder? In ieder geval heb je weer twee extra punaises nodig om ook de derde poster te kunnen ophangen, zie figuur.
Je kunt voor allebei kiezen, maar als je een vierde poster wilt opprikken, dan ben je in de tweede situatie beter uit! Immers, het kost je dan slechts 1 extra punaise, terwijl je in de eerste situatie twee extra punaises moet gebruiken.

Zoals de meeste inzenders ook aangeven, lijken we voor het ophangen van de posters in de vorm van een vierkant de minste punaises nodig te hebben. Natuurlijk is dit alleen maar mogelijk als we 1,4,9,16,... posters hebben. In de andere gevallen moeten we uitgaan van een zo groot mogelijk vierkant, en de rest van de posters zo handig mogelijk aan de zijkant plaatsen, zie figuur.
In deze figuur zijn we uitgegaan van een 3 bij 3 vierkant, waaraan we nog drie posters hebben toegevoegd. Als we nog meer posters willen ophangen, dan gaan we verder als in de derde figuur.

Nu is er weer een vierkant ontstaan, waar we weer volgens dezelfde procedure mee door kunnen gaan. Zo vinden we dat voor 33 posters minstens 46 punaises nodig zijn.

De algemene oplossing

Het echte probleem was het vinden van een formule voor een willekeurig aantal posters, zeg n. In het geval dat n een kwadraat is, is het antwoord duidelijk: er zijn X punaises nodig! Maar wat als n geen kwadraat is? Als we onze eerder besproken opprikmethode volgen, dan zien we dat we eerst een zo groot mogelijk vierkant moeten opprikken, zeg van k² posters. Hiervoor hebben we (k+1)² punaises nodig. Dan blijven er nog m = n - k² posters over, wat er maximaal 2k kunnen zijn. Als nu m tussen 1 en k, dan hebben we voor deze extra posters nog eens 2 extra punaises nodig voor de eerste, en 1 extra voor elke volgende; in totaal m+1 punaises extra. Als m tussen k+1 en 2k dan hebben we zelfs m+2 extra punaises nodig, want voor de (k+1)-ste poster zijn ook 2 extra punaises nodig, voor de overige weer 1. Zie de onderstaande tabel.

n	P(n)	n	P(n)	n	P(n)
1	4	11	19	21	32
2	6	12	20	22	33
3	8	13	22	23	34
4	9	14	23	24	35
5	11	15	24	25	36
6	12	16	25	26	38
7	14	17	27	27	39
8	15	18	28	28	40
9	16	19	29	29	41
10	18	20	30	30	42

Tabel 1 Het aantal benodigde punaises P(n) voor n posters. De functie P(n) springt steeds met 2 na kwadraten en getallen van de vorm k(k+1)