Maths Olympiad Prep

Library / /54 of 75

Combinatorics Difficulty 5.6 AIME, harder Prove it Italy

Problem:

A 1000-piece puzzle can be assembled by fitting the pieces together one after another, so as to insert each new piece into the portion of the puzzle already assembled, or by building several groups of pieces and then joining these together. Each joining (of two single pieces, or of two groups, or of a piece to a group) counts as one move. What is the minimum number of moves needed to complete the puzzle?

Solution

Solution:

The answer is 999. We prove by induction that in order to build a core of nn pieces, n−1n-1 moves are necessary, however one proceeds. The claim is clearly true for a puzzle consisting of a single piece. Suppose that this claim is true for all cores with fewer than nn pieces. The last move to be performed in order to build a core of nn pieces will be the joining of two cores of mm and n−mn-m pieces. By the induction hypothesis, building these two cores required m−1m-1 and n−m−1n-m-1 moves respectively. In total the moves are therefore:
(m−1)+(n−m−1)+1=n−1. (m-1)+(n-m-1)+1=n-1 .
Hence, to build the whole puzzle, 999 moves are needed in every case.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.