Re: Zer0's Conundrum #4 Well i did have a proof. and cash means nothing to me xD I nearly have more cash than everyone else has posts :lol: Basically theres 99 squares. 99/7 = 14. Leaving One square empty on each row. If tiles were placed starting from square 1 -> to the end. And there would be 1 square empty on each column. 98 of these squares could be covered up. Which however hmm means there is 99 x 2 ways. = 198 ways of doing it?
Re: Zer0's Conundrum #4 Man, you guys are epic failing at the rules...one entry per contestant...show a proof...this isn't difficult. I'll update with an answer in a bit. EDIT: ANSWER: First consider a single 1 x 99 row. 14 1 x 7 tiles will be used in order to cover 98 of the 99 spaces. Since 14 tiles were used, each of these tiles can be shifted such that there are 15 different locations within that row that could be left empty: 1, 8, 15, ..., 92, 99. Now, simply extend this along the second axis, essentially saying that you can fill all spaces of the 99 x 99 square except for a single column (just by stacking a particular 1 x 99 row 99 times), and there are 15 different possible columns to be left blank. This uses 1386 of your 1400 tiles. Now, within each column, it just becomes another 99 x 1 situation where there are 14 1 x 7 tiles to use, leaving 15 locations within that column that can be left blank. So, 15 x 15 = 225 different locations that can be left blank EDIT 2: I just realized the question asked for the positions, not the number...hopefully this still counts, because you can intuit the answer from what I have said... Positions x = 1, 8, 15, 22, ..., 92, 99 for each y = 1, 8, 15, 22, ..., 92, 99 can be left blank
Re: Zer0's Conundrum #4 Mk Ice Nine is by far the closest of everyone so far. So Ice Nine, you showed that those positions are some possible positions for the empty square. Can you show that those are the ONLY possible positions? +10 cash for getting this far Will award another 10 if you can complete the above proof
Re: Zer0's Conundrum #4 Hmm, I'm not sure I can prove that this is the only method that can be used to fill all but 1 space. It just kind-of makes intuitive sense that since the blocks are 1 x 7, then if you try to fill the 99 x 99 square in anything other than multiples of 7, you will not use all of the pieces and there will be more than 1 square left over. I'm sorry, I don't think I have a proof to say that other squares cannot be left open other than that this method does not allow it. EDIT: It likely has to do with the rigid bondaries of the square, due to the fact that if pieces could wrap around the borders instead of being limited, then any square could be left open. Heh, no idea. And I have to go for lunch for a couple hours...so I'm done with this problem
Re: Zer0's Conundrum #4 This is the hard part of the problem Well, I'll tell you that your answer is correct. I'll give people until Friday evening to come up with the full proof before revealing my solution.
Re: Zer0's Conundrum #4 *sigh* I wish I knew more about the parity/coloring method... Maybe I'll get around to thinking more about it later... EDIT: ANSWER: Okay Zer0...you forced me to figure it out. Thank you Anyway, the following utilizes a parity argument: Visualize a 99 x 99 board. Color each row 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, ..., 0, 1, 2, 3, 4, 5, 6, 0 (99 rows, so it ends on a 0). For those of you who don't know, "color" means assigning each unit in that row with the desired value...so, we have 14 rows of 1s, 14 rows of 2s, 14 rows of 3s, etc, except for 15 rows of 0s. Once you visualize this, realize that no matter how you place a 1 x 7 tile on the board (either vertically or horizontally), the sum of the squares it covers is always going to be 0 mod 7. Vertically, 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 = 0 mod 7 Horizontally, depending on what row you are in, you will get 0, 7, 14, 21, 28, 35, or 42...all of which equal 0 mod 7. Another thing you must realize is that the area of the entire board is equal to 0 mod 7 (14 * 21 = 0 mod 7). So, the area covered by the 1400 tiles that you put down will be 0 mod 7 and the area of the full board is 0 mod 7. This means that the single space left uncovered also has to have a value of 0 (since we only have values 0 through 6). Thus, the space left uncovered can ONLY be in any one of the 15 rows colored 0. By symmetry, we can perform this same method for columns, telling us that the space left uncovered can ONLY be in any one of the 15 columns colored 0. The final answer showing that these specific 225 spaces are the ONLY spaces that can be left uncovered results from the intersection of the 15 zero rows with the 15 zero columns. I hope that suffices, Zer0
Re: Zer0's Conundrum #4 Correct :yup: +15 cash since I'm nice +rep for the coloring solution Contact dark if you want to claim your 50k NP prize You're solution was essentially the one I came up: Color the board with (x+y) mod 7 coloring. Essentially what that means is if you have 7 different colors, color consecutive squares with those 7 colors (wrapping around to the beginning of the next row). Now if you look at the number of each color you have on the board, you should notice that you have 1400 of each color except for the first color you started with (let's call that color Red) which you have 1401 of. Also notice that when you place a 1x7 tile on the board, you cover exactly 1 of each color. That means you the empty square must be one of the Red squares. If you draw out the picture of positions of all the red squares, you'll notice that they fall on every 7th diagonal (this can be easily formalized mathematically, but it should be fairly obvious). By symmetry, if you rotate the board the same diagonal argument can be made so you just take the intersection of the original board and the rotated board. That will get you Ice Nine's answer.
Re: Zer0's Conundrum #4 Omfg I just spent the last fifteen minutes figuring this out, I refresh the page and facepalm. Whatever. I had a visual to go with my proof, but I guess now it's just going to be a handy one for Icenine's proof. Argh... I should have been working on this sooner. Anyways, a really easy way to visualize it is to assume that if the board is indeed tiled 0 - 98 in each direction from the bottom left corner, every square that comes up with both the x and y values as a multiple of 7 is going to be one the possible positions. If you insist on having it tiled 1-99, it just means that every possible position is a multiple of 7+1 for the x and y values. Edit; Icenine's proof owned the crap out of mine, I think, but said basically the same thing =P grats, you rock man.
Re: Zer0's Conundrum #4 Heh, sorry. I think what you have is pretty much what I said in my first post: correct and intuitive, but doesn't really prove the claim. The kind of proof that Zer0 was looking for was more rigorous, although I may not completely understand what you have in your post. Good job though.
Re: Zer0's Conundrum #4 Oh, I didn't bother posting my proof since it'd be embarassing next to how elegant yours was. But you're probably right about it not having the proof for the claim. Yay math! =P