Suppose your roommate asked you to hang an ugly painting on the wall, while he leaves to do some errands. You don’t want to hurt your roommate’s feelings by saying it’s ugly and you don’t want to be responsible for breaking it yourself, but you also don’t want it to be hung up, because of how ugly it is. While your roommate is gone, you come up with an ingenious strategy: you will hang the picture up by two nails, knowing that your roommate will remove one of them (because of how inefficient two nails is). Of course, when he removes this nail, you want the picture to fall and break. Thus, the picture will not stay up, and you won’t be responsible.
Find some way to hang a picture (with the arbitrarily long, infinitely light and thin string already on) on two nails, spaced apart horizontally to the ground, so that when either nail is removed, the picture will fall.
This problem is really interesting in that it can be extended to much more general cases. Solve the Picture Hanging problem for:
- $2$ nails, pulling any $1$ out, as described above.
- $3$ nails, pulling any $2$ out.
- $N$ nails, pulling any $N-1$ out.
- $3$ nails, pulling any $1$ out.
- $4$ nails, pulling any $1$ out.
- $4$ nails, pulling any $2$ out.
- $N$ nails, pulling any $1$ out.
- $N$ nails, pulling any $k$, $1 \le k < N$ out.
What is the minimum number “wraps” needed to accomplish each of the above statements, where a wrap is some amount of a turn around a nail?