EventHorizon

This is similar to "Apples Delivery, Hungry driver" but I heard this form back in elementary school. I also have a few more questions to ask about it. You have 2000 bananas to bring across the desert. You are riding a camel that must eat one banana per meter (ie, you cannot drop all bananas and move the camel like with the apples question). The camel can hold 1000 bananas at a time. Assume that if you go a fraction X of a meter, then the camel eats X part of a banana. Question 1: How many bananas can you bring to a bazaar 1000 meters away? Question 2: How many bananas can you bring to the bazaar (still 1000 meters away) if you started with 3000 bananas? Question 3: How far could your camel go (one way) if you started with 5000 bananas? Question 4: How much further could your camel go than in Q3 if you started with 6000? Question 5: How many bananas would you need to start with to be able to reach a bazaar 2000 meters away? Question 6: How many bananas would you need to start with to be able to make a return trip from the bazaar in Q5? Question 7: If you have a capacity of C and B*C+E bananas (B is a positive integer, 0 <= E <C), how far (one way) can you ride the camel?

Using the metric "the sum over all players of the absolute value of the difference between the players probability and .2", the answer I gave previously still minimizes this. (of course, S and P are interchangeable in the answer, but I chose the one that favors Perry)

I don't make too many GUIs. I wrote this to be commandline. It is most definitely a bit cryptic...I could explain certain parts if you want. To interpret the match-ups....you look at the remaining players and count from left to right (starts with P, S, D, X, E). The winner of the match is placed at the position of the player in the match furthest left. So lets say the line was 1vs2, 0vs1, 1vs2, 0vs1. This means the bracket would be as follows 1vs2 -> S vs D remaining = P, (S vs D), X, E 0vs1 -> P vs (S vs D) remaining = (P vs (S vs D)), X, E 1vs2 -> X vs E remaining = (P vs (S vs D)), (X vs E) Ovs1 -> ((P vs (S vs D)) vs (X vs E)) I didn't write it to figure out the number of byes needed....I just sorted based on the metric then evaluated them until I found a valid one. zarball.zip

c++, using visual studio .net 2003 I wrote it to output a comma separated value file, and then used excel to help interpret it.

I coded this up....and if anyone is supremely interested I could post the code.

For part 2, What function are you using for "as close as possible"? Difference between high and low probabilities? Ratio of high and low? mean square error? Greatest deviation from average? Most entropy? You are dealing with a probability mass function after all. It doesn't seem to me to have a solution where all are equal.....but I could be wrong. Here's a stab at part 3.

I believe I have come up with a counter-example for being able to cover any 5 out of 6 points on a sphere. (i.e., 5 is the most holes that can work and still have n-1 covered in a well-placed hemisphere) Let four of the points form a square (just so that the points are not all on a circumference and so that the square has some area). If you take each of the those points and look at the point opposite them (through the center of the sphere), let this define the area that I will put the other two points. First let the new points be at the average of two consecutive corners of the new square (formed by the opposing points, not by the original points). Now move these two points closer together by just a little. You can obviously get the four points that form the initial square. To get another point you would need to move the hemisphere enough to uncover at least one of the points that form the square. So if there were 6 holes it would cost at least $9 to guarantee being able to fix the ball without knowing where the holes are in advance.

Cheers, Sam edit: oh crikey, in the time it took me to register we've moved onto six holes? eeek! Exactly. Good Job.

That's actually the method I initially approached the version of this problem that I saw. It doesn't really prove it though.

don't you mean ... 4-1 or 1-4(7$),or 2-3 or 33-2(9$)-worst case. ? For $6, the only way to spend that much is 3 single point patches....and you can only fix 3 holes that way.

A little fyi, a closed hemisphere is one that includes the circumference. So it's like if you chose the northern hemisphere of the earth, it would include the points on the equator.

I wrote this up quick. Change the last sentence to... Without knowing where the holes are, what is the least amount of money Mike can spend and still be guaranteed to repair the lucky game ball? With that said.....here's a quick spoiler for the answer....but can _you_ prove it?

Mike was at a store before the big game. He gets a call from his coach who says that the lucky game ball (a sphere) has 5 small holes in it (each a single point). Without the lucky game ball the team is sure to lose. Mike goes to the ball repair aisle and finds the following: 5 single hole (fixes 1 point) repair kits for $2 each 2 half ball (fixes all points on a closed hemisphere) repair kits for $5 each What is the least amount of money Mike can spend and still repair the lucky game ball?

YW. It didn't take all that much time actually....I'm a Computer Science grad. It was a problem I had thought a bit about before...and it was kinda fun to decide how to implement it in C++ and then to find the answer. It's also nice to know someone else was interested in it too.

The Collatz conjecture (also known as Ulam's problem) ummm.....nope...no answer off the top of my head....but if someone here solves it....I'd love to be a coauthor on the paper

This question requires a few assumptions.... When is the beginning of time? I'll assume 4000bc to appease the new-earth creationists. How quickly can the priests move a single disk? I'll assume it takes one second to move a disk and that it doesn't matter the size of the disk. So, it takes 2^64-1 moves to move the stack.....this is approximately 1.844*10^19. So that amount in seconds is 3.0744*10^17 minutes 5.1241*10^15 hours 2.13504*10^14 days 5.84542*10^11 years (this used 365.25 as days in a year...I know it is a little off) 584542046.1 millenia Well.....that's a lot of time. So I guess my answer would be just about 584542046100 A.D.

As for the window closing. I wrote it to be run from the dos prompt (it is easier to do batch processing that way). The program finishes once the answer is printed, but you could always add in a pause of some sort (two getchar()'s ? or System("pause")) if you can recompile the code. When running from the dos prompt you can also just give it the number of towers and disks on the commandline (eg, "hanoi.exe 4 6"). As for not being able to follow the code.....I assume you mean the C++ code and not the pseudocode...here's a bit of a walkthrough as to what it is doing. * deep breath * I wrote a method to store the list of positions into a single integer (index2num), and one to get it back again (num2index). The index array holds this list of disk positions. The node class is just there to be a linked list. This is used to do the breadth first search. It is used as a queue (first in first out). I first allocate an array to hold every possible state that can be reached (states[]), this is used to store the "parent state" of each state....basically it is how I reached that state. I use this after the goal state is found to print back the sequence of moves. I put the first state (0 0 0 0 0, in the case of 5 disks) onto the queue, and mark that the initial state's parent is itself (0). When printing back you will notice I stop when 0 is found then outside of the while loop print off the initial state. Here's where the main loop begins... I look at the state in the front of the queue and fill index with it's disk positions " if (current) { if (index[disks-1]) break; } " I check to see if I'm in the goal state. If I am I exit the loop. This goal state is only halfway (once the biggest disk is not on tower 0) since once the biggest disk is moved the rest if fairly trivial. This also makes this it run a good deal faster. Then I loop through all valid moves (loop through disks, if there is a smaller disk on me or on the tower I want to move to, it is invalid) and add them to the queue marking their parent state in the states array (so they won't be added again later and to know how I got there). I pop off the node I was looking at and delete it. And then redo the loop. Breadth first search will find the shortest path to any node/state. Which means the least number of moves. * gasp * Hope that helps....

I had an off-by-one error in my pseudocode (should have been nCr(t-3+group,group)), and I can extend the method to allow 0 disks (no moves needed). [spoiler=Why stop at 4? --correct...hopefully ] hanoi.zip first, nCr(x,y) = x!/((x-y)!y!), which is the number of combinations of pool of x objects taken y at a time. So here is a method to determine how many steps it will take to move d (>=0) disks where there are t (>2) towers. Sorry for not being more clear.....but this isn't all that simple. Step 1 - dcount = 0; Step 2 - steps = 0; Step 3 - increment = 1; Step 4 - group = 0; Step 5 - tochange = nCr(t-3+group,group); Step 6 - If (dcount == d) You are done....steps holds the number of steps needed! Step 7 - steps = steps + increment; Step 8 - dcount = dcount + 1; Step 9 - tochange = tochange - 1; Step 10- If (tochange != 0) go to Step 6; Step 11- increment = increment * 2; Step 12- group = group + 1; Step 13- go to Step 5 ok...now to read what roolstar has posted since last night....