Math and Logic Puzzles: Redux

[Felissan]

Spoiler: My answer

Let's call the lines l₁, ... , l_n, and give an orientation to each line.

At any point in time, can define Turbo the Snail's current segment with a n-tuple: if l_i is the line she's currently on, its i^th value is 1 (resp. -1) if she's moving in the line's positive (resp. negative) direction; otherwise, it's 1 (resp. -1) if she's on the left (resp. right) side of l_i from the point of view of someone traveling along it in the positive direction.

Whenever Turbo turns left from l_i to l_j, no value in the n-tuple changes - she doesn't cross, enter or leave any line other than l_i and l_j, and the n-tuple's definition ensures that the i^th and j^th values don't change. Similarly, when she turns right from l_i to l_j, the i^th and j^th are the only values that are changed. As a consequence of this, the product of the n values of the n-tuple is constant throughout Turbo's entire journey.

However, between a segment on l_i being passed both ways, the only variation in the n-tuple is the i^th value being flipped, which means that those two types of movement have opposite values for the product. This means it's impossible to access them both in the same travel.

Turbo the Snail never visits the same segment both ways.

[Gosrir Elmer Odels]

Exactly, very well-put.

[Gosrir Elmer Odels]

Re: balanceable graphs.

1) The claim is not true: consider a disconnected graph.

For connected graphs: since there's finitely many vertices, take one with a maximal value. Than its neighbours must have the same value. Then their neighbours must have the same value. Repeating the process & connectedness yields the desired result.

2) Consider an infinite binary tree „infinite in both directions” (that is a 3-regular infinite tree with the appropriate directions), & use powers of 2 as values of f appropriately. (Do I have to say more?)

3) I have a partial result: If f is a balancing function for our lattice, for any two neighbouring values one is at least one third of the other.

Proof: The two neighbouring values are A & A-ε where A>ε>0. Then the sum of the other three values around 1-ε is 3*A-4*ε, so one of them is at most A-4*ε/3. This means that if a vertex a has a neighbour b such that f(a)-f(b)=ε, then b has a neighbour c such that f(b)-f(c)=ε/3. Therefore f(a)-ε-ε/3>0. Iterating this process we get that f(a)-ε-ε/3-ε/9-...=f(a)-3*ε/2>=0, therefore ε<=2*f(a)/3. If you consider ε=2*f(a)/3, there are all kind of values that get forced, & you get a contradiction, so ε>2*f(a)/3. This is where I am currently.

[Gosrir Elmer Odels]

Okay, I think I have a solution. The square lattice cannot be balanced.

Spoiler: Here's what I did. It's not nice.

a	b	c
d	e	f
g	h	i

Consider the part of the lattice above. Let S be the function that's supposed to balance the lattice. For convience's sake, let S(a)=A, S(b)=B & so on. Wlog E=1, F=ε>=δ, where δ is the greatest such number that if x & y are neighbouring vertices, then S(x)>=δ*S(y). δ exists, trivially δ>=1/4, in the previous post I showed that δ>=1/3. If the lattice is balanceable, δ<1, so wlog δ<1.

Our goal is to find a number bounding B+H+D from above.

Given F=ε, we get than C+I<=4ε-1-δε. By the properties of δ, we get that B+H<=(4ε-1-δε)/δ. Then using the same technique as with the bound of C+I, we get that A+G<=4(B+H)-(2+2δ*(B+H))=(16ε-4-12δε+2(δ^2)ε)/δ.

Now, notice that D<=(min{A,G})/d<=(A+G)/(2δ)=(8ε-2-6δε+(δ^2)ε)/δ^2.

Therefore we get that

4=B+H+D+ε<=(4ε-1-δε)/δ+(8ε-2-6δε+(δ^2)ε)/δ^2+ε=(8ε-2δε+(δ^2)ε-δ-2)/δ^2

8ε-2δε+(δ^2)ε-δ-2>=4δ^2

ε>=(4δ^2+δ+2)/(8-2δ-δ^2), which should be true for all ε>δ, but for all 0<δ<1 there exists ε with δ<ε<(4δ^2+δ+2)/(8-2δ-δ^2). (Check by yourselves.)

[Who]

Why was I not told this existed?

Prove that the derivative of an odd function is an even function and that the derivative of an even function is an odd function.

Let f be a differentiable even function.
f'(x) = \lim_{h\to 0} [f(x+h)-f(x)]/h = \lim_{h\to 0} [f(-x-h) - f(-x)] / h = \lim_{h\to 0} [f(-x+-h) - f(- x)]/ - -h = \lim_{h\to 0} [f(-x+h) - f(- x)]/ -h = -f'(-x), thus f' is odd.
Let g be a differentiable odd function.
g'(x) = \lim_{h\to 0} [g(x+h)-g(x)]/h = \lim_{h\to 0} -[g(-x-h)-g(-x)]/h = \lim_{h\to 0} [g(-x-h)-g(-x)]/-h = \lim_{h\to 0} [g(-x+h)-g(-x)]/h = g'(-x), thus g' is even.

[Who]

Suppose you have 13 real numbers such that if you remove any one of them, you can divide the remaining 12 into two groups of 6 which each have equal sums. Prove that all 13 numbers are equal.

[BNL]

Spoiler: Rationals

Consider a set of and odd number of real numbers good if it satisfies the condition. (for brevity)
Then,
S is good <=> S+r is good for real r (using the same division)
S is good <=> rS is good for nonzero real r (using the same division)

Call S := S+r and S := rS operations. Operations do not change whether a set is good or not

Suppose S contains rational numbers. Multiply them by the lcm of all denominators, so we have only integers, then subtract each element by the smallest element in S.
Now S contains only 0 and positive integers. If there are any odd numbers in S, S is not good because removing either the odd number or 0 will cause the sum of the remaining elements to be odd and they can't be divided into two equal sets.

If S contains only 0 it is clearly good. Otherwise keep dividing S by 2 until there is an odd number (it will happen as positive integers can only be finitely large).

[BNL]

Spoiler: Reals

If we expand to real numbers, we can convert the real numbers into a vector space like this: Let S = {a1,a2,...a13}. Let T0, T1, T2, ... T13 be sets like this: T0 = {}, and Ti = Ti-1 if q1a1+q2a2+...+qi-1ai-1 = ai has a solution in rational q1,q2,...,qi-1, and Ti = Ti-1 U {ai} if there is no solution. Let T = T13 = {r1,r2,...,rk}. Then each ai can be expressed uniquely as q1r1+q2r2+...+qkrk, where q1,q2,...,qk are rational.

Now we have shown that we can equate S to a vector space of k dimensions over the rationals, and we can use the same argument for the proof where S contains rationals.

[Who]

Nice proofs, you got it.

[Gosrir Elmer Odels]

I've found one today, but it's a bit technical, so bear with me.

Spoiler: Basic definitons

A d-dimensional simplex D is the convex hull of d many linearly independent points & the origin in the d-dimensional Euclidean space. (d=2: triangle, d=3: tetrahedron)
A supporting hyperplane of D is a hyperplane (a (d-1)-dimensional subspace of the d-dimensional space) such that D is contained in one of the closed half-spaces. (ie. the hyperplane doesn't slice D up.)
A face F of D is (a) D or (b) the intersection of D with a supporting hyperplane. (note: faces of the triangle: the triangle, the three edges, the three vertices & the empty set. Notice that all faces are (translated) simplices.)
A face is k-dimensional if it can be embedded in the k-dimensional Euclidean space, but not in the (k-1)-dimensional Euclidean space. (Kind of special case: vertices are 0-dimensional)
The solid angle of a face F is ω(F)=lim_{ε -> 0} Vol(B(ε,x) intersect D)/Vol(B(ε,x)) where x is an inner point of F. (ie. for balls small enough the solid angle is the proportion of the ball inside D. eg. the angle of facets is always 1/2. Notice that ω(F) depends on D.)

Spoiler: The question

Prove that for every simplex D the following is true:

sum_{F is face of D} (-1)^{dim F}*ω(F) = 0

This can be done with pretty elementary tools.

[BTD6_maker]

Turbo the Snail is back. This time, there are n circles on the plane. No three circles meet at a point. Turbo begins her journey on one of the circles. She initially moves clockwise along this circle. She moves along a circle until she reaches an intersection. Then she starts moving along the other circle and also changes direction (from clockwise to anticlockwise and vice versa). Prove that, if Turbo's path entirely covers all the circles, n is odd.

[StrangerCoug]

Never mind; I think I had

too

easy a question Let me think of a new one...

[Inferno390]

Turbo the Snail is back. This time, there are n circles on the plane. No three circles meet at a point. Turbo begins her journey on one of the circles. She initially moves clockwise along this circle. She moves along a circle until she reaches an intersection. Then she starts moving along the other circle and also changes direction (from clockwise to anticlockwise and vice versa). Prove that, if Turbo's path entirely covers all the circles, n is odd.

Important question: Do the circles intersect at tangents or no?

[implosion]

Oh yeah I just remembered I had a thing I thought of. So here's another one for anyone interested.

It turns out that if you pick three points at random (uniformly) in a unit square, the expected value of the area of the triangle with those three points as vertices is 11/144. This is a complicated result that involves mean iterated integrals to calculate. See here if you're curious.

Using this, determine the probability that two line segments with endpoints generated at random (uniformly) in a unit square will intersect.

[Who]

Spoiler: Above problem

Randomly generate 3 points, then randomly generate a 4th, then randomize which gets paired with which. If the 4th fits inside the triangle defined by the other three, no matter how you define the line segments they won't intersect. If it doesn't, then there is exactly one which it can be paired with to intersect the line defined by the other two. (Unless it lies on the line generated by two of them, which occurs with probability 0) The probability of it being paired with this one is 1/3. The probability that the fourth falls inside the area defined by the first three is the same as the expected value of the indicator variable, which is the same as the expected value of the area. Thus, the total probability is Expected area/3 = 11/(144*3).

[BTD6_maker]

None of the circles are tangent to each other.

[implosion]

Spoiler: Above problem

Randomly generate 3 points, then randomly generate a 4th, then randomize which gets paired with which. If the 4th fits inside the triangle defined by the other three, no matter how you define the line segments they won't intersect. If it doesn't, then there is exactly one which it can be paired with to intersect the line defined by the other two. (Unless it lies on the line generated by two of them, which occurs with probability 0) The probability of it being paired with this one is 1/3. The probability that the fourth falls inside the area defined by the first three is the same as the expected value of the indicator variable, which is the same as the expected value of the area. Thus, the total probability is Expected area/3 = 11/(144*3).

Not quite - you're missing a case. Right idea, though.

[Who]

On Implosion's triangle problem:

Spoiler: Why I was wrong

Even if one isn't in the triangle formed by the others, that doesn't mean you can't make a triangle out of other points such that the 4th is in the triangle formed by the other 3. If you tried doing the thing I said then the lines would intersect past the edge of one of the segments

Spoiler: Fixed

If and only if you have four points such that no matter which point you choose, it is not in the triangle formed by the other 3, then it is possible to assign the line segments such that they will intersect. Proof of this: Make a triangle, extend the line segments into lines, note that the areas where the fourth point can't be are inside the triangle, and in the areas which meet the triangle at a vertex (As opposed to meeting the triangle at a side). If it's inside the triangle we're done, if it's in one of the areas which ends at a vertex, then that vertex is inside the triangle formed by the other 3.

If A is in the triangle BCD then B is almost surely not in ACD. (And neither is C nor D). In any set of four points, at most one of them can be in the triangle formed by the other 4. Proof of this: Either A or B must be further from line CD, the triangle defined by the closer one clearly cannot contain the further one, since all points in the triangle are closer to CD than the third vertex.

For i=1-4, let x_i be the event "the ith point is in the triangle formed by the other 3". Note that each x_i has probability 11/144. Also, all events are mutually exclusive. Thus, the probability that none of them happen is 1-4*11/144 = 100/144.

[implosion]

You still have to do the last step that you did in your first solution, but yes.

[BTD6_maker]

Here's another problem (although you can still try my earlier one).

Let n be a positive integer. In the Cartesian plane, there is a butterfly on each lattice point with non-negative coordinates (and there are no other butterflies). The neighbourhood of a bitterfly is the (2n+1)*(2n+1) square centred on the butterfly. A butterfly is lonely, comfortable, or crowded, respectively, if the number of butterflies in its neighbourhood is less than, equal to, or greater than half the number of lattice points in its neighbourhood (excluding the butterfly itself) respectively.

Every minute, all lonely butterflies fly away.

a: Prove that after some point there are no lonely butterflies left.
b: Find the number of comfortable butterflies left at this point.

[Tazaro]

Bump;
Before clicking the following link, follow direction #1. https://www.theguardian.com/science/ale ... are-you-on

Direction #1) Without reading the comments therein that preload your mind, Skip down to "

The problem

" in the text at the linked article and read the information until you get to "So, what do you choose?"

Direction #2) Choose whether you side with the philosophy dude A or dude B who opine further down in the article's text--"the philosophy dude"s being Dr. Arif Ahmed or Dr. David Edmonds, who are each giving advice on what you should do about your dilemma. Reason thoughtfully about this kooky conundrum you have found yourself in, supply yourself with a case that's tight enough for you to be convinced by it, and then discuss why you side with the position you side with.

[Kagami]

puzzle!

155619367777177344298579121640577930358466048997080741489502115154736052423438639656322566701951512888971130859442675019505459646950828457775128

divided by

814295694336200301695257325143637445297122644140195688542610298982742658367669506161728178242191616818890832959609127053599963426497407079941861

Answer is nine letters and the name of a San Francisco based company.

[Kagami]

With regard to 70, the argument for taking both boxes is silly. If we assume the super-being is indeed a super-being with super prediction powers, then we accept that she can predict what our philosophical response is to the dilemma when it's presented and so our ultimate decision. It doesn't matter that she can't move it unless the decider is provided some kind of unpredictable input that could influence their decision.

We take both boxes only if we assume she's a fraud. Since this is a philosophical problem that demands we accept the good faith presentation, you take box B and only box B.

[geometry]

Oh yeah I just remembered I had a thing I thought of. So here's another one for anyone interested.

It turns out that if you pick three points at random (uniformly) in a unit square, the expected value of the area of the triangle with those three points as vertices is 11/144. This is a complicated result that involves mean iterated integrals to calculate. See here if you're curious.

Using this, determine the probability that two line segments with endpoints generated at random (uniformly) in a unit square will intersect.

Actually this isn't exactly true - Shoelace formula is your best friend!

[geometry]

Here's a fun one, an EGMO question slightly modified (from last year maybe, but idfk.)

Let there be finitely many lines on the plane, no three of them concurrent. Turbo the Snail (the name is crucial) begins her journey at a point on exactly one of the lines. She moves along the line in one direction until she reaches an intersection. Then she starts moving along the other line, & so on in the same fashion. At the nth intersection she encounters she turns right if n is a prime, & left otherwise. Is there a segment that Turbo the Snail passes through in both directions?

european girls math olympiad?