can /sci/ solve this math contest problem meant for american middle schoolers?
yes, one field.
>>16535918You can tile the board in ways that lead to both loops and it falling off.
>>16535918It's a trick question. You can only tile square boards with side length 2^n with 1x2 tiles.
>>16535974Wait I'm a retard but I figured it out. You can tile it but the only tiling that will work will always cause the robot to fall off.
>>16535976This is the only possible way to tile the given board and will always cause the robot to fall off.
>>16535980It is not. You can rotate those two pieces of your left
>>16535990FUCK
>>16535953Show a tiling that leads to a loop then
>>16535918this answers sketchy bc it doesnt even involve 2018 but, for the robot to stay on it would have to form a cycle somewhere, the area of the region trapped in the cycle is odd and thus not tile-able. so no?
>>16535918It's easy to prove that1. If there is such loop, such loop can be converted to a rectangle loop2. The rectangle loop has 2m+1 side length, and thus have 2m-1 inner length3. The area inside the rectangle loop has area (2m-1)*(2n-1) which is odd and can't be tiled by 2x1 dominoes
>>16536007/thread
>>16536007>such loop can be converted to a rectangle loopThis is a statement that needs to be proven. How would you for example convert something like pic related into a rectangle loop?
>>16536045You prove bits like left can be converted to bits like right. It's straight-forward as each side is also 2m+1
>>16535918because the board has finite area, either the robot eventually encounters the same tile twice (loop) or falls offhowever, any loop will necessarily enclose a shape with odd area, which cannot be tiled with 1x2 piecestherefore, loops cannot exist and the robot always falls off
>>16536561>however, any loop will necessarily enclose a shape with odd areahow do you prove this using techniques that a smart middle schooler without internet could figure out though? i got a proof using the fact that the perimeter has winding number +-1 but i doubt that middle schoolers could use this property in a math contest
Yes, it could, because it's on dominos, not the board.
>>16536683>how do you prove this using techniques that a smart middle schooler without internet could figure out though?probably by starting with the smallest possible loop, then the next smallest and realizing it always encloses an odd number of spaces,
>>16536005>the area of the region trapped in the cycle is oddproof? i thought this too, but i don't know how to prove...
>>16535918>could the robot move forevernoany straight run of dominoes covers an even number of blocks, and adding a turn at the end of the run results in an odd number of blocks being covered along the run.since the grid is even x even in size, you'd run into two problems with the tiling; 1) the interior of any closed loop will have an odd number of blocks, and the exterior of any loop will likewise have an axis aligned bounding box that is odd x odd in size. since an odd number can't be divided by an even number, it will be impossible to fully tile the grid using the 1 x 2 dominoes if there is a loop.since no loop is possible, by exhaustion, the robot will run off the grid eventually.
>>16536683i imagine, smallest possible loop as your base case, encloses area 1then assume you have a loop of odd area, show that any way to extend it yields odd areathen i guess you would also have to show that this generates all possible loops
>>16536683>>16537248ackchually for rectangular loops you also have the fact that you can maybe exploint that if your area is even, then one of your sidelengths has to have even length, which doesn't allow for a loop because of the way they have to be structured
>>16535918The smallest loop for which you could create a loop fulfilling the requirements is a simple loop of four pieces with length, width = 3. It cannot be placed on any board without there being a one-square tile.Loops are self-enclosed, hence the only way for you to expand on/alternate the loop is by adding another 3 x 3 square loop to it, such that the previous movement on the 3 x 3 loop A -> B -> C turns into A -> loop 2 minus its one piece overlapping with and identical in direction with B > C. Hence, if the 3 x 3 square loop has 4 pieces, the composition of the 3 x 3 square loop with the other 3 x 3 square loop, such that a new loop results, consists of 6 pieces.All loops made of two-square tiles follow this pattern, hence any loop can be decomposed into segments consisting of only two pieces -> all loops consist of an even number of two-square tiles. We can also see that all loops fit into n x n squares where n is an uneven number. This follows from the smallest loop being 3 x 3 and the addition of another loop expanding its width or length by either zero or two tiles.[math] n x n = n^2 [/math] is an uneven number, subtracting the loop from it, which is an even number of tiles (because it only consistss of two-square tiles), the resulting number m is uneven. m can't be divided by 2, hence there is no way for two-square tiles to fill in the space.
>>16537283>Loops are self-enclosedWtf does that mean?>hence the only way for you to expand on/alternate the loop is by adding another 3 x 3 square loop to it, such that the previous movement on the 3 x 3 loop A -> B -> C turns into A -> loop 2 minus its one piece overlapping with and identical in direction with B > C. Why?
>>16535918I add the assumption that the board is completely and seamlessly filled with dominos.that comes with restrictions to the board size and also restrictions on how to fill the board with dominos (you cant just start at a random place and place a domino and expect the board to get seamless).I will ignored those restrictions here, our board will be seamless and 2018x2018.I assume the starting point is random.each placed domino stone offers exactly two possible ways to cross it.a border stone which is perpendicular to the edge (in direction of length 2) will always have one way to fall of when you enter it.and since the stones at the four corners need to be perpendicular to one of the four edges this will always be the case for at least 4 stones.so there are always stones at the edges that will make the robot fall off the board.and stones at the edges that are save will always lead to stones that make you fall off the board.the size of the dominoes means that no cyclical paths are possible.if you imagine a recurring path of the robot on four dominoes, you will notice that the center is a single square and cannot accommodate a domino.this fact remains unchanged even with a larger pathes or with a more complex path.it can therefore be concluded that no repetition patterns can arise regardless of the choice of starting point or arrengement.and it can be concluded that any path there is cant have all four movement directions leveled.so the last option left for a permanent path of the robot would be a permanent random path.however, this requires a leveled change of movement direction in all four directions, otherwise a delocation will occur and the robot will approach a boarder edge (shift).answer:no, the robot will always fall off the board. after 2036162 moves or probably even less at the latest.
>>16537286>Loops are self-enclosedStupid way of saying that a loop divides the board into two parts, the area outside of it and the area inside of it. I should have simply called it an enclosure.>Why?The idea is to look at the most simple case and then show that any loop can be created by simply variating, by means of deleting one piece of the original loop (which I forgot to mention) and then adding the new loop to it (where you have to delete the one piece that overlaps with the pieces of the original loop minus the one piece you deleted. The point is that you want to go through the new curve which is the added loop minus the one overlapping piece. It's easy to show that any loop can be constructed that way because any loop can be changed in a way so as to either remove "curves" or add new ones to it such that the newly-added curves is bent towards the inside of the enclosed area. Do that finitely many times until you arrive at a 3 x 3 loop.
>>16537316I claim there is a maximum of 3023 moves. :)
>>16535918a loop made like this could work, I guess. each piece is made of height 4 squares (=2 dominoes) so it's possible. the tracks would be 2010/2 dominoes tall.
>>16537371I hope I'm not doing someones homework...btw, a better answer would be to find a figure that works boh ways (up and down), and maybe even one that works in every direction and also can be built with a width that is a multiple of 2
>>16537371nope
>>16536052Go on, prove it then if it's so straightfoward.
>>16537377that's... not how you would use it, but yeah, there is a flaw nonetheless.you could just insert a (horizontal) line of blocks at one corner though
>>16537388that line will cause drouble.
>>16537394prove it
>>16537396>>16537316somebody can do this by sorting this.I can see that from the information given.
>>16537398that anon is assuming that:1. you can't sort the board or2. the robot will be placed in a random squarefor 1: that's a ridiculous assumption, but my example here >>16537371 is a counter example: there is a layout in which it is possible that the robot will loop for eternity, andfor 2, we need to find a layout in which a robot will always fall in a loop-making circuit. mine is a start
>>16535918The answer is it will fall off. The even patterns will eventually fall off (see pic) and the odd patterns either leave a 1x1 gap or require a board size evenly divisible by 5.Therefore it's not possible.Mathematical proof? Question doesn't ask for one. It doesn't even ask for why. It just asks for an answer.
>>16537414see >>16537371 >>16537388
>>16537408not assuming what you just posted.your layout cant be applied to a <even number> x <even number> board.just show us, you dont need much to do so.
>>16537427>>16537371I just checked and yeah, it doesn't work, I'd be left with one empty square.t.brainlet, I guess
>>16535918No, whatever matter it's on would eventually decay and it would fall off.
>>16537423See the thing I already mentioned?> the odd patterns either leave a 1x1 gap or require a board size evenly divisible by 5.>Therefore it's not possible.
>>16535918Only if a side of the board is a multiple of 3. 2+1+8=11 thus the robot will fall.
>>16537459>Only if a side of the board is a multiple of 3Why?
>>16537479because any direction he walks into is 2n+1.
>>16537814How can a direction be a number? What is n?
