EPTMath Puzzles - Page 8
| Forum Index > General Forum |
|
Malmis
Sweden1569 Posts
| ||
|
lightman
United States731 Posts
| ||
|
Catyoul
France2377 Posts
On June 18 2005 07:01 lightman wrote: The triangle problem is still unanswered I think I've pretty much answered it. Now coming back to it with a good night (or should i say day) sleep, it's pretty straightforward to find a direct formula for each element. k(p,n) = k(p,n-1) + (n+1-p) + max(n+1-2p,0) = k(p,n-2) + (n-p) + max(n-2p,0) + (n+1-p) + max(n+1-2p,0) = k(p,p-1) + (p+1-p) + ... + (2p-1+1-p) + (2p+1-p) + (2p+1-2p) + .. + (n+1-p) +(n+1-2p) To get from 2nd to 3rd line, I've just went back step by step, k(p,p-1) is of course 0 so everything is known in that line. The separation at n=2p-1 comes from the fact that it's the point where n+1-2p gets >= 0 so we have to include the second recurrence term. Actually we have 2 cases I should have separated earlier. Either n+1-2p >= 0 or not. If n >= 2p-1, we have the sum written above. If n <= 2p-1, the max(n+1-2p,0) is always 0, so it actually simplifies to : k(p,n) = (p+1-p) + ... + (n+1-p) So, we have 2 cases. 1. n <= 2p-1 : k(p,n) = sum(k+1-p) for k=p -> n = (n+1-p)(n+2-p)/2 2. n >= 2p-1 : k(p,n) = sum(k+1-p) for k=p -> 2p-1 + sum(2k+2-3) for k=2p -> n = p(p+1)/2 + (n+1-2p)(n+2-p) Tadaaaaaaa. | ||
|
Catyoul
France2377 Posts
BigBalls : I think your conjecture is false, doesn't work for 7 and 11 for example. Nice intuition however, there definitely seems to be something with powers of 2 and even powers of 2. Looks like some fractal-like structure going like this : 1 -> 2^(2p+1) : block A 2^(2p+1)+1 -> 2^(2p+2) : block B 2^(2p+2)+1 -> 2^(2p+3) : A, B thus giving something like : 1-2-4-----8--------16----------------32-------------------------------------------------------64 A B AB CDCD ABABCDCD E F EF EFEF GHGH EFEFEFEFGHGH 64---- ...-- 128 ABABCDCDABABCDCDEFEFEFEFGHGHEFEFEFEFGHGH Gotta go now, but I'll be back to formalize and try to prove it  | ||
|
Catyoul
France2377 Posts
f(n) = f(n+2^(2k)) for k such as 2^2k > n The structure described in my previous post is a direct consequence of this. | ||
|
Sorrow_eyes
United States1007 Posts
GL HF. | ||
|
BigBalls
United States5354 Posts
all lights that are hit twice are on, hit 4 times, hit 6 times. so powers of 2, 4, 6, etc however, powers of 4,6 are subsets of powers of 2. thus, all powers of 2 are on | ||
|
Sorrow_eyes
United States1007 Posts
On June 18 2005 00:45 gg2w wrote: Take 1 coin from stack 1, 2 coins from stack 2, etc. Weigh the 55 coins. If the weight of a genuine coin is y, the correct weight should be 55y. Then deduce which stack is the counterfeit based on how much you are off by. nicely done  | ||
|
Sorrow_eyes
United States1007 Posts
On June 18 2005 19:36 BigBalls wrote: sorrow eyes, its not that hard even. all lights that are hit twice are on, hit 4 times, hit 6 times. so powers of 2, 4, 6, etc however, powers of 4,6 are subsets of powers of 2. thus, all powers of 2 are on hmm, im sure that number 1 bulb got hit once, and its on. 2 got hit twice, and its off T_T enlight me...[ | ||
|
BigBalls
United States5354 Posts
so 1 is hit 0 times after that the ones that are on after that are ones that are hit an even number of times. this means they are even powers, so they are x^(2y) = (x^y)^2, so all square numbers stay on | ||
|
Sorrow_eyes
United States1007 Posts
On June 18 2005 19:45 BigBalls wrote: i mean after the initial hit when theyre all on. so 1 is hit 0 times after that the ones that are on after that are ones that are hit an even number of times. this means they are even powers, so they are x^(2y) = (x^y)^2, so all square numbers stay on Hi again and all the other numbers stays off? for example, 24 is not a square number but it still stays on switch on/off 1...............on 2...............off 3...............on 4...............off 6...............on 12.............off 24.............on | ||
|
BigBalls
United States5354 Posts
you forgot 8 | ||
|
Sorrow_eyes
United States1007 Posts
thx for prompt replies | ||
|
BigBalls
United States5354 Posts
a number after 1 will be hit by itself. thus, to stay on, it needs either 1, 3, 5, etc factors. factors come in pairs unless they are squares thus the only way for a number to have an odd number of factors is if its a square | ||
|
Sorrow_eyes
United States1007 Posts
Thanks a bunch Math major pwns doesnt it  K I got a question: Background: A king has a tiger, he hid the tiger behind one of the five doors. A knight wants to marry the king's daughter, he must open one door and kills the tiger. The King says: Young worrier, the tiger will ALWAYS caught you by suprise when you open the door which contains it. The knight thoughs: Because the tiger will always caught me by suprise, it must not be in the last door because when I fond the first four doors are empty, it must be in the last one, and that's not a suprise at all. So then it must not be in the second last door for the same reason... and the third to the last door, and goes on... It is no tiger behind anydoors! The knight proceed happily to open each door, convinced that there isnt any tiger... and once he opens the second door, a tiger jumps out, and that completely suprised the knight. Which part of the knight's thought is flawed? | ||
|
BigBalls
United States5354 Posts
right now im doing research on difference sets Basically, start with a Group G of order v. A subset D of G is a (v,k,lambda) difference set if Delta D = lambda * (G-0). Delta D = (d-d', d,d' are in D, d!=d'). So basically, the set Delta D has each non identity element of G exactly lambda times. Let me give you an example. D={1,2,4} is a (7,3,1) difference set in Z7. Delta D = {1-2,1-4,2-1,2-4,4-1,4-2} = {6,4,1,5,3,2} (addition in Z7) = {1,2,3,4,5,6}, which is 1 copy of each non identity element in Z7. It's interesting stuff, my professor is basically the leading guy in the field. | ||
|
keke
Canada186 Posts
| ||
|
lightman
United States731 Posts
On June 18 2005 08:40 Catyoul wrote: I think I've pretty much answered it. Now coming back to it with a good night (or should i say day) sleep, it's pretty straightforward to find a direct formula for each element. k(p,n) = k(p,n-1) + (n+1-p) + max(n+1-2p,0) = k(p,n-2) + (n-p) + max(n-2p,0) + (n+1-p) + max(n+1-2p,0) = k(p,p-1) + (p+1-p) + ... + (2p-1+1-p) + (2p+1-p) + (2p+1-2p) + .. + (n+1-p) +(n+1-2p) To get from 2nd to 3rd line, I've just went back step by step, k(p,p-1) is of course 0 so everything is known in that line. The separation at n=2p-1 comes from the fact that it's the point where n+1-2p gets >= 0 so we have to include the second recurrence term. Actually we have 2 cases I should have separated earlier. Either n+1-2p >= 0 or not. If n >= 2p-1, we have the sum written above. If n <= 2p-1, the max(n+1-2p,0) is always 0, so it actually simplifies to : k(p,n) = (p+1-p) + ... + (n+1-p) So, we have 2 cases. 1. n <= 2p-1 : k(p,n) = sum(k+1-p) for k=p -> n = (n+1-p)(n+2-p)/2 2. n >= 2p-1 : k(p,n) = sum(k+1-p) for k=p -> 2p-1 + sum(2k+2-3) for k=2p -> n = p(p+1)/2 + (n+1-2p)(n+2-p) Tadaaaaaaa. First of all I can't really understand your solution but from what I read, you don't make any difference between the triangle positions and that is your mistake. The problem is as follows: ![[image loading]](http://img158.echo.cx/my.php?image=sol0001pk.gif) So now you have to distinguish between the standing triangles and the upside down triangles. The standing triangles satisfy this relation Parallel lines 1 2 3 4 5 6 7 8 Total 0 1 1 1 3 1 4 2 6 3 1 10 3 10 6 3 1 20 4 15 10 6 3 1 35 5 21 15 10 6 3 1 56 6 28 21 15 10 6 3 1 84 7 36 28 21 15 10 6 3 1 120 while the upside down triangles follow this table: Parallel lines 1 2 3 4 5 6 7 8 Total 0 0 0 1 1 1 2 3 3 3 6 1 7 4 10 3 13 5 15 6 1 22 6 21 10 3 34 7 28 15 6 1 50 so in the end we get something like this: Parallel lines : 1 2 3 4 5 6 7 8 9 Number of triangles 1 5 13 27 48 78 118 170 236 It is easy to observe that in table #1, the number is very similar to the result you posted, (n+1)(n+2)/2. Therefore, the total number of triangles is the SUM from 0 to n, this agrees with your reasoning. S(i=0,i=n) (i+1)(i+2)/2 = (n3 + 6n2 + 11n + 6)/6 now what you miss was to take the upside down triangles: to achieve this we calculate the succesive differences of each term of the new B serie Difference: 1 3 7 13 22 34 50 70 95 1ª 2 4 6 9 12 16 20 25 2ª 2 2 3 3 4 4 5 3ª 0 1 0 1 0 1 generalizing: 3rd difference = (1+(-1)n)/2 2nd difference = 2 + S(i=0,i=n-1) 3rd difference = (2n+5-(-1)n)/4 1st difference = 2 + S(i=0,i=n-1) 2nd difference = (2n2 + 8n+ 7 + (-1)n)/8 thus Total Number of upside down triangles is 1 + S(i=0,i=n-1) 1st difference = [(4n3 + 18n2 + 20n +3)/48] - [(-1)n/16] and finally we add the standing up triangles with the upside down triangles to achieve the number of all triangles: [4n3 + 22n2 +36n + 17 - (-1)n]/16 which is the correct answer Please let me know if you have any questions | ||
|
decafchicken
United States20060 Posts
1. One day, a person went to horse racing area, Instead of counting the number of human and horses, he instead counted 74 heads and 196 legs. Yet he knew the number of humans and horses there. How did he do it, and how many humans and horses are there? 2. y = log x If y = 10, then what is x? 3. 10*9*8*7*6*5*4*3*2*1 = 10! Can this be true?! Why or why not? 4. If 1/2x +1/2(1/2x + 1/2(1/2x +1/2(1/2x + ... = y, then x = ? 5. What place in this world can have their temperatures Fahrenheit and Celsius equal? | ||
|
iamke55
United States2806 Posts
| ||
| ||
