Math and Logic Puzzles

[serrapaladin]

That's correct. Note that you want to put layers closer together where the cone is broader.

Actually working this out fully (which I also didn't do...) is fairly instructive as a problem in multivariate calculus, as you need to set all derivatives to 0, solve the resulting set of equations, and show that the Hessian is negative definite.

[Sudo_Nym]

We are airy little creatures,
All of different voices and features:
One of us in glass is set,
One of us you'll find in jet,
Another you may see in tin,
And the fourth a box within;
If the fifth you should pursue,
It can never fly from you.
What are we?

[NJAC]

Vowels

[Scigatt]

You can play a game on the Euclidean plane where you place points on the plane, and are scored on the number of distinct lines with at least three distinct placed points on them. You are given five distinct points that score to 0, and are allowed to place four more. In the 'generic' case, what is the highest score you can get?

[Mitillos]

You can always guarantee at least 8 points. Draw the lines through each pair of given points. Since there are five such points, no three of which are colinear, there will be 5C2 = 10 such lines. Each such line will be parallel with at most 1 other line, and coincide at one of the given points with 6 other lines (three at each of its given points). This leaves at least 2 lines it can cross at a point that is not already given. This means that in the worst case there are 10 points, each of which can be chosen for a score of +2. (Note that it's impossible for two lines to cross at a given point, without being defined by it, as the five original points score 0.) So, even if no three crossing points are colinear, and no two crossing points are colinear with a given point that does not define them, you are guaranteed to get a minimum of 8 points, by picking four of these crossing points.

This method is very naive, of course, so it's possible that there's some other way that can give you more points.

[serrapaladin]

More riddler fun:

You have a camel and 3,000 bananas. (Because of course you do.) You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?

[serrapaladin]

Can't really think right now, but I think there's a second part to mitillos' solution that proves the bound is tight.

It involves something like:

9 points make at most 9C2 = 36 lines. Three noncollinear points make three lines, while three collinear points make one line. So if you wanted 9 collinear triplets, you would have 18 lines. In the given construction, you start with 5C2 = 10 lines, and for some geometry reason, every new point adds at least 3 new lines (under some condition like not being the same as a previous one, and not being along a previous triplet line). Hence it's not possible to get fewer than 19 lines, and thus it's not possible to get 9 or more collinear triplets.

[Scigatt]

Can't really think right now, but I think there's a second part to mitillos' solution that proves the bound is tight.

It involves something like:

9 points make at most 9C2 = 36 lines. Three noncollinear points make three lines, while three collinear points make one line. So if you wanted 9 collinear triplets, you would have 18 lines. In the given construction, you start with 5C2 = 10 lines, and for some geometry reason, every new point adds at least 3 new lines (under some condition like not being the same as a previous one, and not being along a previous triplet line). Hence it's not possible to get fewer than 19 lines, and thus it's not possible to get 9 or more collinear triplets.

This is wrong. It is possible to get 9 in the generic case.

[NJAC]

More riddler fun:

You have a camel and 3,000 bananas. (Because of course you do.) You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?

Can I carry some bananas or only the camel can carry bananas? If yes, is there a limit of bananas at a time I can carry?

[Gamma Emerald]

It is impossible to sell any bananas, because your camel demands a banana for every mile, and the mile-to-bananas carriable ratio is a perfect one-to-one.

[Rhinox]

That's not true. For example, you could take 1000 bananas half way, drop the 500 remaining off, go back and repeat twice and now you've got 1500 bananas and only 500 miles to travel. You can then easily get 500 of those bananas to the market from there.

I'd guess the best you could do would be something like taking 1000 bananas 666 2/3 miles, dropping off 333 1/3 bananas, and going back for 2 more trips to get the rest so now you have 1000 bananas with 333 1/3 miles left to go. That gets you to market with 666 2/3 bananas left uneaten.

[Sudo_Nym]

Put point A at 1/3 the distance, and point B at 2/3 the distance.

Pick up 1000 bananas, walk to point A. The camel eats 333 bananas on the way, so leave the remaining 667 bananas at A. Go back to the start, pick up 1000 bananas, go to point B, picking up 333 bananas at A on the way. The camal eats 333 bananas from A to B, so now there's 1000 bananas at the start, 334 bananas at A, and 667 bananas at B. Go back to start, pick up 1000 bananas. Walk to the end, picking up 333 bananas at A, and 333 Bananas at B. Now you have 1 banana at A, 334 at B, and 667 bananas at the finish. So it's possible to get 667 bananas to the end point this way.

Put A at 1/4, B at 1/2, C at 3/4:

Code: Select all

Start
3000  2000  1000      0     0

A
0      750    500   250     0

B
0        0    750   500     0

C
0        0      0   750     0

Finish 
0        0      0     0   750

So you can get more bananas with 3 stops than with 4. I don't care to work out right now what the optimal number of stops is, but there's at least those two worked out.

[BNL]

Can't really think right now, but I think there's a second part to mitillos' solution that proves the bound is tight.

It involves something like:

9 points make at most 9C2 = 36 lines. Three noncollinear points make three lines, while three collinear points make one line. So if you wanted 9 collinear triplets, you would have 18 lines. In the given construction, you start with 5C2 = 10 lines, and for some geometry reason, every new point adds at least 3 new lines (under some condition like not being the same as a previous one, and not being along a previous triplet line). Hence it's not possible to get fewer than 19 lines, and thus it's not possible to get 9 or more collinear triplets.

This is wrong. It is possible to get 9 in the generic case.

Spoiler:

Let the points be A, B, P, Q, X.
Let AB meet PX at C, AC meet PQ at R, AQ meet BP at Y, BR meet CQ at Z.
By Pappus Theorem on lines ABC and PQR, X, Y, Z are collinear, and you have nine lines.

Haven't disproved 10 lines yet, though that should be trivial.

[Rhinox]

Sudo-

I'd guess you could make a stop every mile, extending the logic that more stops = better. A pattern starts to form like below:

Code: Select all

Start
3000 2000 1000    0    0    0  ... 

A
   0  999  998  997    0    0  ... 

B
   0    0  999  998  994    0  ... 

C
   0    0    0  999  998  991  ... 

D
   0    0    0    0  999  998  ... 

E
   0    0    0    0    0  999  ... 
.
.
.

From there, the top number in each column loses 3 each time and runs out when the 999 pile has been pushed to 336 miles away from the start, and there is a 2nd pile 335 miles from the start with 996 bananas. Since there are only 2 piles now, the top pile loses 2 bananas each move until it runs out with a pile of 999 bananas that are 834 miles from the start, or 166 miles from the finish. From there, 999-166=833 bananas make it to the market. Not sure if its best, but best so far...

That can kinda be simplified I think:

Take 3 trips from start to point A which is 333 1/3 miles away and drop off 666 2/3 bananas each trip. Point A now has 2000 bananas. Take 2 trips from point A to point B which is 500 miles from point A and drop off 500 bananas each trip. Point B now has 1000 bananas and is 166 2/3 miles away from the market. 1000-166 2/3 = 833 1/3 bananas.

(and this saves the labor of picking up and putting down piles of bananas every mile for a 1000 miles lol)

eta: I think that's the optimal solution. As long as NumberOfBananas/1000>2, you're going to lose 3 bananas for every mile you move the bulk (because it takes 3 trips to move the bulk), no matter how you break up the trips, so it makes sense to move them to a point where NumberOfBananas/1000=2 exactly so as to not lose 3 bananas per mile any longer than needed. Then, you're going to lose 2 bananas per mile moving the bulk until NumberOfBananas/1000=1. And then lose just 1 banana per mile the rest of the way.

[Scigatt]

Spoiler:

Let the points be A, B, P, Q, X.
Let AB meet PX at C, AC meet PQ at R, AQ meet BP at Y, BR meet CQ at Z.
By Pappus Theorem on lines ABC and PQR, X, Y, Z are collinear, and you have nine lines.

Spoiler:

That should be AX meet PQ at R

[Sudo_Nym]

Suppose 2n points are arranged on a plane so that no three are collinear, and then half are colored red and half are blue. Will it always be possible to connect a red dot to a blue dot, in pairs, so that none of the connecting lines intersect?

[BNL]

Suppose 2n points are arranged on a plane so that no three are collinear, and then half are colored red and half are blue. Will it always be possible to connect a red dot to a blue dot, in pairs, so that none of the connecting lines intersect?

I think you meant each red dot to a blue dot.

Spoiler: Solution

Yes.

There are n! ways to connect red dots to the blue dots, which is finite. Therefore, there must exist a way to connect the dots such that the total length of lines drawn is minimal (if tie, choose any one). This configuration cannot contain any pair of intersecting lines, because if there is, reconnecting that pair to uncross those lines will decrease the total length of all lines, contradicting the fact that it is the configuration with minimal total length.

[StrangerCoug]

Suppose 2n points are arranged on a plane so that no three are collinear, and then half are colored red and half are blue. Will it always be possible to connect a red dot to a blue dot, in pairs, so that none of the connecting lines intersect?

I think you meant each red dot to a blue dot.

Spoiler: Solution

Yes.

There are n! ways to connect red dots to the blue dots, which is finite. Therefore, there must exist a way to connect the dots such that the total length of lines drawn is minimal (if tie, choose any one). This configuration cannot contain any pair of intersecting lines, because if there is, reconnecting that pair to uncross those lines will decrease the total length of all lines, contradicting the fact that it is the configuration with minimal total length.

That's not my interpretation of his problem. I had interpreted it to mean exactly one red dot is connected to exactly one blue dot.

[Sudo_Nym]

Spoiler:

BNLP's solution is correct. StrangerCoug's interpretation of the problem is correct, but BNLP's logic works just fine in either case.

[Sudo_Nym]

Suppose we randomly select x and y on the interval [0, 1], uniformly distributed. What is the probability that mean(x,y) <= .1?

[Who]

Spoiler:

The probability that mean < .1 is the probability that sum < .2, so:
y+x<.2
y<.2-x
Geometrically, the whole space is a 1x1 square, this is a triangle in the bottom left corner, with vertices (.2,0) (0,.2) and (0,0). Total area of this is .2^2/2 = .02
Thus the probability is .02.
(< and <= are same by nonatomicness)

[Mitillos]

Let's bring back the prisoners and hats.

There is a countably infinite number of prisoners, who are being offered the chance to be released. They will each have a black or white hat placed on their head, and be arranged in a line, so that each prisoner can see all the prisoners and hats ahead of him, but not behind or on him (don't worry about how they will manage to see an infinite number of people, just go with it). Then, starting from the person who can see everyone else, they will each make a guess as to whether their hat is black or white. Those who get it right can leave, but the rest will be killed. The prisoners can confer for a strategy in advance, but not during the event.

1) For any given fraction, find a strategy that saves at least all but that fraction of the prisoners.
2) Find a strategy that saves all but a finite number of prisoners.

[Who]

Spoiler: 1)

For any fraction x, find an n such that 1/n<x. Divide the prisoners into groups of n, use standard prisoners and hats solution for each of those groups. (First prisoner out of the n says black if even number of black hats in his group, white if odd, then next prisoner knows what his hat is from that, etc.)

[Zorblag]

Let's bring back the prisoners and hats.

There is a countably infinite number of prisoners, who are being offered the chance to be released. They will each have a black or white hat placed on their head, and be arranged in a line, so that each prisoner can see all the prisoners and hats ahead of him, but not behind or on him (don't worry about how they will manage to see an infinite number of people, just go with it). Then, starting from the person who can see everyone else, they will each make a guess as to whether their hat is black or white. Those who get it right can leave, but the rest will be killed. The prisoners can confer for a strategy in advance, but not during the event.

1) For any given fraction, find a strategy that saves at least all but that fraction of the prisoners.
2) Find a strategy that saves all but a finite number of prisoners.

Part 1 be pretty easily doable.

Spoiler: Outline of a solution

Simply have the prisoners grouped in increasing group sizes and use whatever parity strategy has been used before for these problems here. The easiest would be to start with one prisoner, who might die, then two, of which only one can die, then three, of which only one can die and so far. The possible number of deaths for the first n groups be n, but that includes n(n+1)/2 total prisoners. The limit as n approaches infinity of n/[n(n+1)/2] is zero, so this would give you the desired fraction saved for any fraction you like (well, assuming the fractions be between 0 and 1.)

Part 2 Toll no has any particular insight on.

-Zorblag R`Lyeh

[Who]

I'm pretty sure that part 2 is impossible. Working on a proof.

The proof isn't working, meaning it's probably possible, or at least, if it's impossible it's for a different reason than I was trying to use.