A problem that requires sheer ingenuity

A long thin strip of paper is 1024 units in length, 1 unit in width, and is divided into 1024 unit squares. The paper is folded in half repeatedly. For the first fold, the right end of the paper is folded over to coincide with and lie on top of the left end. The result is a 512 by 1 strip of double thickness. Next, the right end of this strip is folded over to coincide with and lie on top of the left end, resulting in a 256 by 1 strip of quadruple thickness. This process is repeated 8 more times. After the last fold, the strip has become a stack of 1024 unit squares. How many of these squares lie below the square that was originally the 942nd square counting from the left?

Other urls found in this thread:

tutorialspoint.com/compile_java8_online.php
twitter.com/SFWRedditImages

k

Bumping while I work on it

I got that it was in position 594, and there are 430 beneath it. I'm garbo at arithmetic, but I think my process is at least sound.

Shit, I did it so that the right fold is beneath rather than above. Give me a few minutes.

I guess it would just be position 430 with 594 beneath. I still think I McFucked up the calculations though.

By which I mean 431 with 593 beneath. I'll shut up now. I'll also show my process if it's still off.

It's 7th from the bottom meaning that 6 squares are underneath it

Source: I solved it in Java:
public static void main(String []args){
int length = 1024;
final int fold = 2;
int leftPlace = 942;
int bottomPlace = 1;

while(length>1){
length = length/fold;
if(leftPlace>length){
bottomPlace++;
leftPlace = length*fold - leftPlace;
}
}
System.out.println(bottomPlace);
}

Hold the phone, I just wrote a recursive algorithm that gives me 11 as the place from the bottom, giving 10 squares underneath number 942

public class PaperFolder{

public static int findBottomPlace(int length, int leftPlace, int bottomPlace){
System.out.println(length);
if(length == 1){return bottomPlace;}
length = length/2; //halves the length and finds midpoint at the same time
if(leftPlace > length){
bottomPlace++;
leftPlace = length*2;
}
return findBottomPlace(length, leftPlace, bottomPlace);
}

public static void main(String []args){
int length = 1024;
int leftPlace = 942;
int bottomPlace = 1;

bottomPlace = findBottomPlace(length, leftPlace, bottomPlace);

System.out.println("bottomPlace = " + bottomPlace);
}
}

Ah my problem was in the line "leftPlace = length*2;"

When replaced with the correct "leftPlace = length*2 - leftPlace;" you get 7 as the position from the bottom again confirming that there are 6 squares under number 942

Sorry, but it's pretty easy to count out that far without an algorithm, and it's not right.

Bottom is 1
2nd from bottom is 1024
3rd is 513
4th is 512
5th is 257
6th is 768
7th is 767

I don't know anything about programming, so I don't know where to begin helping, but unless I'm totally misunderstanding how the folding works, 942 can't be 7th.

In case anyone is still in this thread and wants to know how I approached the problem:

You first need to find the point at which the paper is folded. You can do this by dividing the length (at the beginning 1024) by 2. In the first case the paper is folded with squares 1-512 in the bottom layer and squares 1024-513 in the top layer (from left to right). Therefore you have to notice that every time that you fold the paper in half, the squares to the left of this folding point retain their place from the bottom, and if they're above the folding point they get folded over above and so move up one place in position from the bottom (ie the squares between 1024 and 513 are now in position 2 in the vertical hierarchy).

Therefore all you need to do is for each successive folding figure out if the square you're interested in is above the folding point. If so, you're going to fold it up one spot and invert it's place from the left relative to the horizontal length of the paper before it's folded.

Doing this ten times gives that square number 942 when the paper is not folded is in position 7 when the paper is fully stacked upwards

Oh, I see where you went wrong now though. It's only in the first round of folding that numbers only go up one layer if they're past the folding point. For instance, in the second fold, the folded half of the first layer becomes the fourth layer in the vertical hierarchy, not the second.

Yeah I went totally wrong actually. The number 7 is how many times the 942nd square is folded over before it's no longer above the threshhold. There's some uncounted number of times that it's not folded so knowing this I just need to find what position it's in after the seventh folding and we're set

by "uncounted number of times" I mean 3 times because you're only folding 10 times derp

Just fixed this program by fixing these lines:
added new parameter for the findBottomPlace method, a fourth int called "thickness" which represents the number of times the paper has been folded. Then I replaced "bottomPlace++" with "bottomPlace = bottomPlace + thickness;" to represent that whenever the square is folded over, it goes up the same number of positions as the current number of times the paper has been folded over. I also added "thickness++;" right before the final return line since the paper will be folded no matter what the square does.
I initialized thickness as 1

This all gives me that the 942nd square ends up in position 34 from the bottom, leaving 33 squares under it.

>whenever the square is folded over, it goes up the same number of positions as the current number of times the paper has been folded over.

Sorry if I'm misinterpreting what you said, but that doesn't sound right either. Whenever a layer is folded, the value of the new layer is t+1-v where t is the total number of new layers after folding and v is the old layer.

So for instance, if a number is on the 15th layer out of 16, and it's folded upward, it is now on layer 32+1-15= the 18th layer. At least I think that's the case.

Yeah sorry, I guess it was a really bad description of the thickness parameter. "Thickness" is the literal number of layers the paper has. Therefore it's correct to say that a square goes up in position the number of squares of thickness the layer has each time it's folded over. Thickness is also Number of Foldings - 1.

The full code is here if you want to tinker with it. Just have to change the leftPlace parameter in the main method, compile and then execute to check to see if it's correct. It spits out 1 for 1, 2 for 1024, 3 for 512, and 4 for 513 as far as I've checked so I'm confident that this is right.

Code:

public class HelloWorld{
static int findBottomPlace(int length, int bottomPlace, int leftPlace, int thickness){
if(length == 1){return bottomPlace;}
int foldingPoint = length/2;
if(leftPlace>foldingPoint){
bottomPlace = bottomPlace+thickness;
leftPlace = length - leftPlace;
}
thickness++;
return findBottomPlace(foldingPoint, bottomPlace, leftPlace, thickness);
}

public static void main(String[] args){
int length = 1024;
int bottomPlace = 1;
int leftPlace = 942;
int thickness = 1;

System.out.println(findBottomPlace(length, bottomPlace, leftPlace, thickness));
}
}

you can go to this website to compile it
tutorialspoint.com/compile_java8_online.php

>Java

I transposed it to bash

#!/bin/bash

length=1024
fold=2
leftPlace=942
bottomPlace=1
thiccness=1

while [ "$length" -gt "1" ]; do
(( length = length/fold ))
if [ "$leftPlace" -gt "$length" ]; then
(( bottomPlace = bottomPlace + thiccness ))
(( leftPlace = length * fold - leftPlace ))
fi
(( thiccness++ ))
done

echo "$bottomPlace"

>thicc
give us your results for
1, 1024, 512, 513, 942, and 943 please

>in Java

Fucking kill yourself

>1
1 (one)

>1024
2

>512
3

>942
34

>943
24

>513
4

Also, 512 and 513 are supposed to be 4 and 3 respectively, but my script says differently

Yeah I just realized that this guy was right, bottomPlace doesn't just go up by thickness. Fuck back to the drawing board

Here's my pen and scratchpaper approach. I'm interested to see if codeanon can get his program together.

Been working on this all night brother
The sleepiness is affecting my speed haha

The answer I got was 890
Will post the start of the stack order I got for inspection

>The answer I got was 890
>Will post the start of the stack order I got for inspection
So I guess 889 pieces would be under it, and its place in the stack is the 890th spot. Pic is the stack starting from the bottom

512 and 513 are in the wrong spots. Think I fucked up somewhere

None.
The sheet had no thickness to begin with, as it wasn't specified in the problem.

So it turns out these anons are right (though I don't know what that second guy means by 430 beneath it)

The way the problem works is like this:
If the square's position from the left is before the half point then folding the paper will have no effect on it, preserving its "leftPlace" and "layer" location. If it is past the half point then both its layer and leftPlace are inverted according to the following formulas:
Given that thickness is the current thickness of the paper
newLayer = thickness*2 + 1 - oldLayer
newLeftPlace = length + 1 - oldLeftPlace

I'm going to post two pieces of code, first a recursive method and then a while loop that give the correct results for any square.

public class FoldingPaper{
static int findLayer(int length, int layer, int leftPlace, int thickness){
if(length == 1){return layer;}
int foldingPoint = length/2;
thickness = 2*thickness;
if(leftPlace>foldingPoint){
layer = thickness + 1 - layer;
leftPlace = length + 1 - leftPlace;
}
return findLayer(foldingPoint, layer, leftPlace, thickness);
}

public static void main(String[] args){
int length = 1024;
int layer = 1;
int leftPlace = 942;
int thickness = 1;

System.out.println(findLayer(length, layer, leftPlace, thickness));

while(length>1){
length = length/2;
thickness = thickness*2;
if(leftPlace>length){
layer = thickness + 1 - layer;
leftPlace = length*2 + 1 - leftPlace;
}
}
System.out.println(layer);
}
}

Fixed it. There are 593 squares below the 942nd
Will post updated code segment

4 people getting the same answer must mean we fucking solved it.

Updated code

It's 2AM and I just spent hours solving some stupid ass computational problem. Ima go smoke a blunt and think about my life.

It does. Good job anons

>I don't get what he meant by 430

I did the problem so that I was folding the right fold underneath rather than above the left fold. All I had to do was flip the stack over to get the right answer.

Also, I'm the same guy in both posts.

Oh makes sense, you solved the problem 4 hours in and then we still spent another 4 hours making sure lel

Also, if you figured out that the square was in the 594th spot from the bottom then how could there only be 430 squares under it?

Oh, 430 is how many squares it has above it. When I was doing it backwards, I was thinking of squares in terms of their position from the top of the stack since 1 would be the topmost rather than bottommost square. When I flipped it, I still stated its position from the top (actually 431) even though there was no real reason to and it was kind of confusing in retrospect.

512
ez

wait, it should be 0 because 2^10 is 1024

If 0 was the answer that would imply that 942 is at the very bottom and just given that the square marked 1 is by definition to the left of the half point for any folding, it is unaffected by any folding process, and therefore always stays at the bottom. I know you're trolling but at least put some effort into it

Or to be more clear, my original answer was 594 from the top with 430 squares underneath, and then I successively corrected my mistake in the next three posts.

I will kill myself if its not 128.

Man, how do you develop the creativity to solve original problems like this?

I took a used wad of tissue I found on the floor and folded it a couple of times so I could visualize the folding. Then I drew it on MS Paint so I could look at it clearly

Mm I figured out the 16 case first on paper and used that to write my program.

By not being a stupid undergrad.
I got 7, scrolled through the thread a bit, and saw a bunch of morons arguing about java.

Like, what the fuck? It took me 5 seconds to figure out the answer.