Origami Puzzle Challenge

[andrewkirk]

RULES:
1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

CHALLENGE:
We are given an oblong piece of paper whose long edge has length ##n## cm. It has a fold, parallel to the short edge, ##k## cm from one of the short edges, which we'll call the left edge.

Show that, provided ##k## and ##n## have no common prime factors other than 2, we can always execute a sequence of folds that ends by making a fold that is parallel to the left edge and 1cm away from it. The rule for making a fold is that we can only make it at the midpoint between two existing fold marks or edges. We use the word mark for a line that is either a fold mark or an edge. The way of making a fold midway between two marks is:

1. If both marks are fold marks, fold the paper underneath at the leftmost of the two fold marks, so that the leftmost mark becomes an edge.

2. Bring the left edge across to align with the right mark then flatten and press down. This makes a new fold mark midway between the two existing marks.

Here's an example, courtesy of user @ddddd28, who came up with this problem.

The paper is ##11## cm on the long side and has a fold mark ##5## cm from the left edge. Call that Fold 1.

Make Fold 2 halfway between Fold 1 and the right edge. Fold 2 is ##8## cm from the left edge.

Make Fold 3 halfway between Fold 2 and the left edge. Fold 2 is ##4## cm from the left edge.

Make Fold 4 halfway between Fold 3 and the left edge. Fold 3 is ##2## cm from the left edge.

Make Fold 5 halfway between Fold 4 and the left edge. Fold 4 is ##1## cm from the left edge.

For extra credit, show that if ##k## and ##n## haven a common prime factor other than 2, a fold ##1## cm from the left edge cannot be achieved under these rules.

 

[jedishrfu]

Do you have a diagram to go with the problem? Sometimes origami instructions are hard to follow.

 

[andrewkirk]

I know what you mean. I'm terrible at following origami instructions. Unfortunately, I'm afraid a legible diagram of this is beyond my drawing skills. But, at the expense of losing touch with the nice paper-folding aspect of the problem, it can be re-expressed as a purely mathematical problem as follows:

Starting with the collection of integers ##\{0,k,n\}## where ##0<k<n## and ##k,n## have no common prime factors other than 2, show that we can introduce a finite number of additional numbers into the collection, one at a time, so that it eventually includes the number 1, where each new number introduced must be the arithmetic mean of two numbers already in the collection. Then show that this is not possible if ##k,n## have a common prime factor other than 2.

 

[Greg Bernhardt]

PF T-shirt to the member who solves this :)