De winnaar van de breinbreker van november-december 2021 is Lins Denaux. Proficiat! Hij leverde een mooie graaftheoretische oplossing voor de breinbreker. We feliciteren ook Bart Van Gasse, Steven Van Overberghe en Jasper Devreker voor hun correcte inzendingen.
Oplossing:
Zij t het aantal weggegeven T-shirts. We bewijzen via sterke inductie op t > 0 dat 7t+6 ≤ n.
Voor t=1 moeten er duidelijk minstens 13 pizza's besteld worden voordat iemand een T-shirt kan winnen. Stel nu dat de uitspraak geldt voor alle t'<t. Stel, uit het ongerijmde, dat er een situatie bestaat met n < 7t+6. Kies n minimaal waarvoor dat het geval is. Noem Adam de allereerste persoon die een pizza heeft besteld. Dan heeft Adam een T-shirt gewonnen (anders kunnen we hem weglaten en is n niet minimaal). We verdelen alle anderen in twee verzamelingen X en Y. Zij Eva één van de twee mensen die Adam overtuigd heeft en stel X gelijk aan de verzameling van mensen die Eva overtuigd heeft, eventueel via een keten, Eva inclusief. Verdeel al de rest in groep Y. Stel nx=|X| en ny=|Y| en zij tx resp. ty het aantal winnaars van een T-shirt in X resp. Y. Wegens inductie is 7tx+6 ≤ nx en 7tx+6 ≤ nx als tx,ty>0. Maar ook als tx=0 of ty=0 gelden die ongelijkheden (omdat Adam in elke groep minstens 6 mensen heeft overtuigd). Dus is 7t+6 = 7(tx+ty+1)+6 = 7tx+6+7ty+6+1 ≤ nx+ny+1=n toch geldig, een strijdigheid.
Het aantal weg te geven T-shirts is dus ten hoogste n/7.