9
$\begingroup$

Alice and Bob started to play a game with a piece of A4 paper. Alice is going to cut that paper as she wants and will give it to Bob, then Bob will fold the paper from anywhere he wants. In the game, Alice wants to maximize the visible area so cuts it accordingly, whereas Bob wants to minimize the area after folding.

Game 1

Let's call the area of new piece of paper after Alice works on it is 1 unit. Bob optimally folds this piece of paper once from anywhere he wants to make the paper having the minimum possible area (included all visible area) after this procedure.

What is the maximum area possible if Bob and Alice play the game optimally?


Game 2

It is the same game but this time we start to consider our original paper dimension. That means let's call our A4 area is 1 unit and with the same rules above; (Alice cuts this A4 paper into something, Bob folds it once)

What is the maximum area possible if Bob and Alice play the game optimally?

Game 3

let's call our cut paper area is 1 unit again. and as you guessed it is the same game but this time Alice can cut our A4 paper from anywhere she wants but she can only cut once and this specific cut has to be a straight cut. (you may take any piece you want, bigger or smaller piece of paper)

What is the maximum area possible if Bob and Alice play the game optimally?

$\endgroup$
  • $\begingroup$ Ask clar for game 2, can Alice just cut the paper small enough so the maximum area of Bob will be very small? $\endgroup$ – athin Jan 14 at 8:15
  • $\begingroup$ @athin the idea is the maximize the total unit of area, for game 2 it is 1 unit for A4 paper. if Alice cut the paper small, our area becomes smaller as well which we do not want... or I may have misunderstood your question. $\endgroup$ – Oray Jan 14 at 8:17
  • $\begingroup$ Ah, so we act as Alice here. Ok got it, thanks! $\endgroup$ – athin Jan 14 at 8:20
  • $\begingroup$ So is Alice trying to maximize the area and Bob trying to minimize it? Or vice versa? $\endgroup$ – Deusovi Jan 14 at 8:26
  • $\begingroup$ @Deusovi Alice is trying to maximize the area of folded paper (after bob folds) and cutting the paper accordingly (not only maximizing the area) (Since I asked for "maximum area"). Bob is trying to minimize the folded area. $\endgroup$ – Oray Jan 14 at 8:28
7
$\begingroup$

Game 1

Alice could make it arbitrarily near 1:

The line segments should be made very thin and very long. Each line segment halves the width and doubles the length of the previous one, and is rotated by a fixed small angle.
If the a-th line segment intersects (or overlaps) with the b-th where a<b, the folding point must be in line segment b or b-1. That means there could be only 2 line segments intersecting with line segments with a lower or equal number. Each line could have at most 2 intersection points with a convex shape. And we could count both edges if they are at the endpoints. We also count the case where the folding line crosses at most 2 endpoints and 4 line segments. That's only 32 intersection points. (Actually not this many, but we don't have to prove a smaller number.)
In the worst case, it's technically not a intersection point, but two line segments overlaps exactly, or a line segment overlaps with itself. But we could say they could never have an area bigger than the area of one line segment. That's still negligible if there are a large number of line segments.

A bit too late, but constructed differently.

$\endgroup$
  • $\begingroup$ We all know we could compute the answer for Game 3 by enumerating all the possibilities, but I'm too lazy to do it. And it doesn't seem to have an elegant solution. $\endgroup$ – user23013 Jan 14 at 13:08
5
$\begingroup$

Game 2

I think Bob can always get to at least 0.5 by imagining the original A4 and folding so that the original paper would go exactly in half. No matter how Alice cuts the paper, the remaining area can be no larger than 0.5.

A4 folds

Note that if neither of the halving folds is available to Bob, the area after the cut can be no more than 0.25 which is way worse for us (as Alice) than 0.5.

Alice can get arbitrarily close to 0.5 by nipping an extremely thin slice off one side.

$\endgroup$
  • $\begingroup$ sorry, but my intention was cut paper area as 1 unit, not A4 area. could you reconsider your answer accordingly please? $\endgroup$ – Oray Jan 14 at 9:51
  • $\begingroup$ @Oray Ah, ok. Hmm... $\endgroup$ – jafe Jan 14 at 10:00
  • $\begingroup$ @Oray It still works for game 2, I think? $\endgroup$ – jafe Jan 14 at 10:16
  • 1
    $\begingroup$ it is indeed :) $\endgroup$ – Oray Jan 14 at 10:28
  • 2
    $\begingroup$ And this is also the solution for Game 3! $\endgroup$ – athin Jan 14 at 11:30
5
$\begingroup$

Game 1:

Answer: arbitrarily close to 1
First, Alice should draw a point on the paper sheet. Then another. Then another. After that Alice keeps adding different random points to the sheet, somehow watching out that no 4 points become ends of a symmetrical quadrangle (rectangle, rhombus, equilateral trapezoid or this "kinda-rhombus" with a single symmetry) and that no 3 points get on the same straight line. Seeing how she has infinite options for a point, she can always find such.
Having stopped at N points, now we have such a position, that by folding the sheet we can't get more than 3 points into points (our best options are: 1) have 2 points max on fold, yet connect no more points 2) Have two points connected with fold and one on fold). That's the intention.
Next, Alice draws circles with arbitrarily small radius, centered in these points. The radius should be small enough that we can't even intersect more than three circles while folding the paper, just as with points.
Next step is obvious - we connect the circles with a web of infinitely thin lines, so that the sheet is connected, yet it's area is still concentrated at N circles. Than we cut it out carefully.
Since Bob can intersect 3 circles max, the area of resulting sheet will be decreased by around 3/N with all his efforts. Taking arbitrarily large N we can create arbitrarily bad shape for Bob.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.