EventHorizon
-
Posts
578 -
Joined
-
Last visited
-
Days Won
8
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by EventHorizon
-
-
Spoiler
The error happens when he takes the square root of both sides.
(4-9/2)^2 = (-1/2)^2 = (1/2)^2 = (5-9/2)^2
Or more simply...
(-1)^2 = (1)^2, take the square root of both sides gives -1 = 1. Except it doesn't!
sqrt((-1)^2) = |-1| = |1| = sqrt(1^2)
-
1
-
-
Spoiler
In both xp2008's and my solutions, you don't scan over the same range twice, once for each parity. You increase the range by the scale factor every time you switch the parity.
-
Some maximum permutations/combinations
SpoilerStarting Configuration Length, Max Permutations, Max Combinations
0,8,8
1,7,7
2,12,12
3,20,20
4,45,36
5,104,64
6,245,112
7,795,240
8,2907,511
9,10401,1088
10,33997,?Some code (yay for global variables.... yeah... i was lazy)
Spoiler#include <stdio.h>
#include <string.h>
#include <cstdlib>#define MAX_MOVES 100
unsigned char used_dir[MAX_MOVES*2+1][MAX_MOVES*2+1];
unsigned char path[4*MAX_MOVES];
unsigned char path_max_p[4*MAX_MOVES];
unsigned char path_max_c[4*MAX_MOVES];
int mode;
int length;
int conflength;
int max_p_found;
int max_c_found;
int start_length;
int moves;
int more_moves;
int clength;
int moves_target;
int x;
int y;
int permtotal;
int combocount;
float combototal;
int dirs[9][2] = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}, {0,0}};void set_used(int dir){used_dir[x][y] |= 1<<dir;}
void clear_used(int dir){used_dir[x][y] &= ~(1<<dir);}
char is_used(int dir){return used_dir[x][y] & (1<<dir);}
int is_used_node(int dir){return used_dir[x+dirs[dir][0]][y+dirs[dir][1]] == 0 ? 0 : 1;}
void print_path(){for(int i=0; i<length; i++) printf("(%i)",path[i]); printf("\n");}void move(int dir)
{
if (!is_used_node(dir)) moves++;
path[length++] = dir;
set_used(dir);
x += dirs[dir][0];
y += dirs[dir][1];
set_used((dir+4)%8);
}void unmove(int dir)
{
clear_used((dir+4)%8);
x -= dirs[dir][0];
y -= dirs[dir][1];
clear_used(dir);
length--;
if (!is_used_node(dir)) moves--;
}void cmove(int dir)
{
clength++;
clear_used(dir);
x += dirs[dir][0];
y += dirs[dir][1];
clear_used((dir+4)%8);
}void cunmove(int dir)
{
clength--;
set_used((dir+4)%8);
x -= dirs[dir][0];
y -= dirs[dir][1];
set_used(dir);
}void combo_rec()
{
if (clength == length) {combocount++; return;}
for (int i = 0; i < 8; i++)
if (is_used(i)) {cmove(i); combo_rec(); cunmove(i);}
}void do_combo_check()
{
combocount = 0;
clength=0;
int savex = x;
int savey = y;
x = y = MAX_MOVES;
for(int i = 0; i < start_length; i++) cmove(path[i]);
combo_rec();
for(int i = start_length-1; i >= 0; i--) cunmove(path[i]);
combototal += 1.0f / (float)combocount;
x = savex;
y = savey;
}void permute_rec()
{
if (moves == moves_target)
{
if (mode != 4) do_combo_check();
if (mode==1) printf("%i,%i ",length,combocount);
if (mode==1) print_path();
permtotal++;
return;
}
for(int i = 0; i < 8; i++)
if (!is_used(i)) {move(i); permute_rec(); unmove(i);}
}void config_rec()
{
if (length == conflength)
{
permtotal = 0;
combototal = 0;
start_length = length;
moves_target = moves + more_moves;permute_rec();
if (mode == 2)
{
print_path();
printf("Permutations = %i\n", permtotal);
printf("Combinations = %i\n", (int)(combototal+0.0001f));
}if (permtotal > max_p_found) {max_p_found = permtotal; memcpy(&path_max_p,&path,conflength);}
if (combototal > max_c_found) {max_c_found = combototal; memcpy(&path_max_c,&path,conflength);}
return;
}int min = 0;
int max = 8;
if (length == 0) {max = 2;}
if (length == 1) {min = path[0]; max = path[0]+4;}
for(int i = min; i < max; i++)
if (!is_used(i)) {move(i); config_rec(); unmove(i);}
}
int main(int argc, char *argv[])
{
if (argc != 4) {printf("Usage 1: lines 1 <config> <more>\nUsage 2: lines 2 <length> <more>\n<config> is an initial configuration like 7436\n<length> is the length of initial configurations to search over\n<more> is the additional moves taken.\n"); return 0;}
mode = argv[1][0]-'0';
x = y = MAX_MOVES;
length = moves = 0;
permtotal = 0;
combototal = 0;
memset(&used_dir,0,sizeof(used_dir));
more_moves = std::strtol(argv[3],0,10);
if ((more_moves < 1) || (more_moves > 10)) printf("More moves out of bounds.");
if (mode == 1)
{
while (1)
{
int nextdir = argv[2][length] - '0';
if ((nextdir < 0) || (nextdir > 7)) break;
move(nextdir);
}
start_length = length;
moves_target = moves + more_moves;permute_rec();
printf("Permutations = %i\n", permtotal);
printf("Combinations = %i\n", (int)(combototal+0.0001f));
return 0;
}if ((mode == 2) || (mode == 3) || (mode == 4))
{
conflength = std::strtol(argv[2],0,10);
if ((conflength > 50) || (conflength < 0)) {printf("Length out of bounds.\n"); return 0;}
max_p_found = max_c_found = 0;config_rec();
printf("Most permutations = %i : First found = ", max_p_found);
for(int i=0; i<conflength; i++) printf("(%i)",path_max_p[i]); printf("\n");
printf("Most combinations = %i : First found = ", max_c_found);
for(int i=0; i<conflength; i++) printf("(%i)",path_max_c[i]); printf("\n");
return 0;
}
printf("Usage 1: lines 1 <config> <more>\nUsage 2: lines 2 <length> <more>\n<config> is an initial configuration like 7436\n<length> is the length of initial configurations to search over\n<more> is the additional moves taken.\n");
}code also attached.
Example usage
SpoilerI named the executable "lines"
The first argument is the mode. Mode 1 will expect argument 2 to be a string of numbers 0-7 representing the initial configuration, and argument 3 will be the number of moves to add on to it.
Mode 2 will search over all initial configurations of length <argument 2>, adding <argument 3> number of moves to it. I added a mode 3 (quiet) and mode 4 (quiet and don't find combinations).
So if I run "./lines 1 7436 1", it would show all the possibilities starting with the initial configuration of 7436 (the first two numbers on the line are the length of the path and how many different permutations use the same lines (used to calculate combinations)), then list the totals of 41 permutations and 36 combinations.
If I run "./lines 2 5 1", it would list the number of permutations and combinations for all initial configurations of length 5 (though not the ones that start with directions 2-7, and only half the possibilities for the second line direction. This is to cut down on reflections/rotations that would be equivalent.). It would end by printing:
"Most permutations = 104 : First found = (0)(3)(4)(4)(7)
Most combinations = 64 : First found = (1)(4)(5)(4)(1)" -
So people don't need to register for an account at mathhelpboards.com to see those images...
On 9/27/2020 at 10:53 AM, Laubarr said:Hello All,
See picture below:
There exist an infinite plane with infinite number of dots. For sake of argument, let's assume they are 1 inch away from each other.
However, below(on your far left) you can see 3 lines already made. The last line is the yellow one.
What you see on the right, are all combinations of possible moves. Move is defined as structure of lines until you reach an empty dot.
Thus, there are 6 combinations of single line(on top). While on bottom you see 10 combinations. 5 of them moves with 2 lines, and 5 with 3 lines.
Total # of combinations is 16.
So far so good?
Well the basic unsolved question are:
* Does formula exist to calculate total number of combinations(16 in this case) just by looking at the initial graph of 3 lines?
** Does formula exist to show the breakdown of all combinations (6 for single line, 5 for 2 lines, 5 for 3 lines?
*** is 16 the biggest number of combinations that you can make from 3 line starting configuration? For instance: Try to calculate # of combinations (1 lines, 2 lines, 3 lines) from this initial variation:
To not spoil the fun, i will just say there is more than 16. So is this the best solution? How we can prove that this is the best we can do? Obviously we can prove that just by doing all 3 line configurations by hand, but what if we take it to next level? What's the best 4 line configuration and how many combinations it has? How about 5,6.7...(n) ? The tree expands quite rapidly, and also few things need to be explained:
Combinations vs Permutations:
Above, there are 4 lines as starting configuration. In this case, there are 36 combinations OR 41 permutations. The reason is because you can go from A > B > C > D or C > B > A > D. Once again, is there a formula to calculate combinations (36) and Permutation(41) from any starting configuration?
Notation + Final info to consider:
Using above notation, you can notice that each configuration is unique and might have different #s of combinations and or permutations. For example:
Anyone with any input, either mechanical or potentially writing a code to get the answers How many combinations/Permutations for each variation with up to 10 lines as a starting configuration, would be greatly appreciated. If your program can handle bigger starting configurations, that's even better!
Thank You and enjoy!
-
Spoiler
Assuming that the path the monk takes is exactly the same going up and down (no forks in the path, no loops unless taken in the reverse order and direction), and there is no teleportation involved, then there is a point on the path where the time would be the same for the monk going up or down.
Let P1(t) be the progress along the path from 0=bottom to 1=top of the mountain for the monk on day 1 at time t. Similarly P2(t) for day 2. Then F(t) = P1(t) - P2(t) is the difference in the monk's location at time t between the two days. Both P1(t) and P2(t) are continuous (since the monk doesn't teleport
), so their difference F(t) is continuous. F(7am)=0-1=-1, and F(7pm)=1-0=1. Using the intermediate value theorem we know there exists a time t such that F(t)=0. It would be at this time that the position the monk is on the two days would be the same.
-
1
-
-
Looks like a variation of the Siamese method for constructing n-odd magic squares.
-
How about...
SpoilerSince you have an hour worth of burn time, you need to keep 4 burn points going at all times. Start both ends and some point in the middle, which will burn in two directions, burning. This will start 4 points burning. Once two burn points meet, choose a point in the middle of the remaining rope to start on fire to return it to 4 points burning. Repeat until the rope is all gone.
-
1
-
-
Spoiler
(a) Brown is half of pink (eq 1)
(b) Pink - 4 is half of Sundae (eq 2)
(c) Sundae = Pink + Brown (eq 3)
2 * (Pink - 4) = Pink + (Pink/2) => 2 Pink - 8 = Pink + Pink/2 => Pink - 8 = Pink/2 => Pink = 16 (from a,b,c)
After finding the value for pink, it's pretty easy...
Brown = 8 (from eq 1)
Purple = 2 (from eq 1, 4*Purple = Pink/2)
(16-4) /2 = 2 * Cone => 6 = 2 * Cone => Cone = 3 (eq 2)
Sundae = 16 + 8 = 24 (eq 3)
Didn't need eq 4, but you can verify using it... Brown + Cone = 11 => 8 + 3 = 11.
-
While the hole that the groundhog starts in is unknown, it is one specific hole and its movements are as described. No matter what hole it starts in, given its described movement, the strategy given will eventually find it. You make it seem like the groundhog can teleport just because it's starting hole was unknown.
Given your "about 17 holes outside" example, it would take just one or two (depending on parity) rounds of area clearing/expansion to get it. It does not matter that there are more holes outside the area, it will eventually be trapped and caught.
-
My thoughts and solutions:
SpoilerSolution 1: If you have one person check, for instance, holes 0 and 3 on alternating days, you can keep the groundhog trapped in holes 1-2. Using this, you can have the other scan over the area being guarded. And once the scan is done, trap progressively larger areas alternating the assumed parity for each time a new area is selected. You can easily choose a multiplicative factor to increase the size of the areas by to make the time spent on the previous areas practically meaningless compared to the new area size, so the groundhog couldn't escape by running away.
Solution 2: Not that the groundhog, if the correct parity, cannot get past the person making the scan of the area. Then you can have one person start at one end of a chosen area and the other at the other end, and if the groundhog has the right parity and is in the area, it will be caught. This is simpler than solution 1 since both checkers have the same job. It also doubles the speed of solution 1.
---Additional thoughts---
Solution 1 was what I initially thought of when coming up with this puzzle. Using this idea you could also have a puzzle like two squares of holes with a shared edge, have one person alternate at the two intersection points and then have the other scan the 3 connected segments for the assumed parity, then clear it again with the other parity.
xp2008's solution was rather interesting. He showed that you didn't even need to have an area trapped if you scan in one direction using both checkers.
Looking at solution 2, you can see that if the line of holes has an end on one side (ie, one sided infinity), you only need 1 person to find the groundhog.
The solutions for my original additions back in the day all had solutions that were rather elegant extensions of the original problem's solution. This one turns out to be the same. Using solution 2, if you center the checking around hole 0 (ie, when one person checks hole x, the other checks -x), start with checking an odd number, and have the scale factor an odd number 5 or more (3?)... it seems much like a simple extension of the solution to the original problem. The requirements of starting at odd hole and having the scaling factor be odd makes the parity naturally alternate with each new area. Also, like how you never need to check holes 1 or 5 in the original, you never check hole 0 in this solution.
-
15 minutes ago, xp2008 said:
To solve the question without knowing parity, we follow almost the same steps, except we change hypothesis of parity alternatively each time we go to next round. And it may take us one more round to find it, because we find it only when in the same parity.
You got it. Well done. I'll post my solutions later.
-
1
-
-
16 hours ago, xp2008 said:
If we know first day's parity then we can. Supposing it was odd, then I will check
- 1 3
- 4 6
- 1 -1
- -2 -4
- 6 8
- 9 11
- ...
Which is to say,
day 4k+1, I check 5K+1, 5K+3
day 4k+2, I check 5K+4, 5K+6
day 4K+3, I check -5K+1, -5K-1
day 4K+4, I check -5K-2, -5K-4
We can see my range is ( -5K-4, 5K+6 ) , while lim ( 5K - 4K) = lim (K) -> infinity, thus we could always find the groundhog in this case.
Unfortunately, that does not work for the known parity case.
Notice day 4 checks even holes, and day 5 also checks even holes. So days 5-8 are checking the wrong parity.
Fixing this, the numbers change such that day 4k+x checks hole 4k+y, so the groundhog can escape by fleeing away from hole 0.
-
20 hours ago, HotRodCow said:
If they started from either end worked to the middle they would eventually find it... provided they lived for eternity
There is no end to start from. Every hole has an infinite number of holes on both sides of it.
And, yes, both you and the groundhog are immortal. Your friend, not so much. Luckily, you'll always be able to enlist a member of his posterity to help check one hole each day, so close enough.
-
Perhaps this question will help move things along...
SpoilerIf I were to tell you on the first day that the groundhog was an odd number of holes away from the origin, could you then find the groundhog with 2 hunters?
-
8 hours ago, Wilson said:
Barring blind luck, I don't think it can be caught with two hunters. Thoughts....
Think minimum required is two teams of 3. From origin one team heads -ve, other goes +ve. Teams can check two new holes each day, whilst preventing the hog from backtracking. They will be moving twice speed of hog so will eventually capture.
SpoilerYou can cut one hunter off your strategy by alternating which direction checks two new holes and which only checks one.
Can anyone find the groundhog using less than 5 hunters?
-
Negative infinity to positive infinity. You could pick any hole to be the origin.
-
There is an infinite line of holes in an infinite field. You know there is a groundhog hiding in one of the holes. You can check a hole once a day. At night the groundhog will move one hole to the left or one hole to the right. Knowing you cannot find the groundhog yourself, you enlist a friend to help. Now you can check 2 holes a day. Can you find the groundhog? If so, how would you do it?
Original: http://brainden.com/forum/topic/11943--/
My Additions: http://brainden.com/forum/topic/12010--/
-
Spoiler
2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2 should do it. 16 checks to get the bug.
I went and found the first time I encountered this puzzle: http://brainden.com/forum/topic/11943--/
Here's my additional puzzles on the same theme: http://brainden.com/forum/topic/12010--/
I just thought of an additional one... will post shortly :)
-
Beat me to it, kudos CaptainEd. I guessed the solution and came up with a proof while trying to get to sleep last night. The first step was inelegant, so I was going to work on it a bit before posting.
SpoilerFirst, show the bottom block of all triangles of height 4 can be found by using the consecutive block coloring rule on the first and last block.
I brute forced it, but reduced the needed examples by relabeling colors and flipping order. This was the part that needed to be done more elegantly. CaptainEd's proof does this part well.
I may have added a step showing that blocks outside of sub-triangles don't influence colors inside the sub-triangles. Fairly obvious.
Then, notice that the 10 block triangle can be seen as 3 height 4 sub-triangles, 2 height 4 sub-triangles under that, and a final height 4 sub-triangle... all with overlapping corner blocks. This new formation is equivalent to another triangle of height 4 because the first step of the proof showed that for triangles of height 4 you only needed to do the coloring rule on first and last blocks. Using the first step of the proof again, the last block of the 10 block triangle is just the coloring rule on the first and last blocks of the height 10 triangle.
Using this method, you can see that for any triangle of height 1+3^n for n=0 to infinity, the last block is simply the coloring rule on the first and last blocks.
I thought it could be interesting to try to find out the minimum number of applications of the coloring rule you would need to do to determine the color of any given block from a triangle of height X based on its height, but haven't thought too much about it. It could be an interesting number sequence. 0,1,3,6,1,3...
This problem reminded me a lot of
SpoilerThe creation of Sierpinski's Triangle by starting with a 1 with infinite 0's on either side, and the next row is made by exclusive or of the two numbers above.
1
11
101
1111
10001
110011
1010101
11111111
etc
-
Spoiler
"I'm a liar or I'm rich."
Liar - Since he is a liar, the statement is true... so the liar cannot say it.
Poor truthful man - Since he is neither a liar nor rich, the statement is false... so he cannot say it.
Rich truthful man - Since he is rich, the statement is true... so he can say it.
-
1
-
1
-
-
Spoiler
Assume Rmax can contain every region of diameter one.
Fit a circle of diameter one into Rmax. Pick any point in Rmax which is not in the circle of diameter one. Now look at the line through this new point and the center of the circle. Notice the distance between the point and the far intersection between the circle and line is greater than one (the diameter of the circle plus the distance to the point). Since Rmax cannot have diameter greater than one, there is no point outside the circle and inside Rmax. Therefore Rmax must be a circle of diameter one.
Now take an equilateral triangle of diameter one. The lengths between each of the three vertices of the triangle is one. The only line segments of length one contained inside the circle are ones that intersect the center of the circle at their midpoint. Then you can fully contain at most one of the sides of the triangle inside the circle. Therefore a circle of diameter one cannot contain an equilateral triangle of diameter one.
Since we've reached a contradiction, Rmax cannot contain every region of diameter one.
-
Spoiler
I have the minimum at approximately 0.2172336282.
That value is cos x, where x solves tan x = pi + x. pi+x being how far the ogre will need to run around the lake of radius 1, and tan x = sin x / cos x = distance along the tangent line of the inner circle of radius f to the edge of the lake divided by f.
As for the distance addition... it sounded more interesting when I wrote it. It may be more interesting starting from the center of the lake (trade-off between movement inside circle of radius f and outside it), but still not that interesting. Though it would be interesting to see the minimum length path for all f. As it approaches the minimum, you'd see more and more spiraling in the circle of radius f.
-
I'd say that the minimum value of f is slightly less than...
Spoiler1/(pi+1)
I'll play around with it a bit to see how much I can lower it. Another interesting addition might be, once the minimum f is found, to find the minimum travel distance (e.g., amount of gas) needed for some f a little higher than the minimum.
-
Spoiler
Chair
How many combinations?
in New Logic/Math Puzzles
Posted
8*6!
extension: 64*6!
Reasoning:
The layout doesn't matter except to know that there are 6 positions/cards.
If there were X unique cards (and ignoring rotations), there are X! possible permutations.
If there are X cards of type 1, Y cards of type 2, and Z cards of type 3, and again ignoring rotation, you could arrange them in (X+Y+Z)!/(X!*Y!*Z!) ways.**
It is easy to see how this can be extended to any number of groups of any size.
Now to deal with the rotations. Each position can be right-side-up or up-side-down. So for each of the ways you can rearrange their positions, there are 2^6 ways the cards could be rotated.
So the answer to the original problem is (2^6)*(2+2+2)!/(2!*2!*2!) = (2^6)*6!/2^3 = 8*6!
The extension is (2^6)*(1+1+1+1+1+1)!/(1!*1!*1!*1!*1!*1!) = 64*6!
One thing to note is the formula for number of combinations is a special case of the above formula(**). So if there are k of the type you are interested in, and n-k others, the number of combinations of n taken k at a time (aka n choose k, or nCk) is (k+(n-k))!/(k!*(n-k)!) = n!/(k!*(n-k)!)