## Math and Logic Puzzles: Redux

This forum is for playing games other than Mafia and Mafia variants.
Felissan
Goon

Joined: April 03, 2015
Location: France
Pronoun: She
Let's call the lines l1, ... , ln, 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 li is the line she's currently on, its ith 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 li from the point of view of someone traveling along it in the positive direction.

Whenever Turbo turns left from li to lj, no value in the n-tuple changes - she doesn't cross, enter or leave any line other than li and lj, and the n-tuple's definition ensures that the ith and jth values don't change. Similarly, when she turns right from li to lj, the ith and jth 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 li being passed both ways, the only variation in the n-tuple is the ith 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.
"Dammit Felissan, making someone lose the game is NOT NICE" - DeathRowKitty 2016

The Tale of Felissan - I'd be willing to revive it if people posted in it

Gosrir Elmer Odels
Goon

Joined: May 20, 2018
Pronoun: He
Exactly, very well-put.

Gosrir Elmer Odels
Goon

Joined: May 20, 2018
Pronoun: He
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
Goon

Joined: May 20, 2018
Pronoun: He
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
Yes?

Joined: March 22, 2013
Location: Third Base
Pronoun: He
Why was I not told this existed?
In post 39, Ircher wrote: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.
Last edited by Who on Wed Jun 13, 2018 1:44 am, edited 1 time in total.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

Who
Yes?

Joined: March 22, 2013
Location: Third Base
Pronoun: He
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.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

BulletNLynchproof
Mafia Scum

Joined: September 16, 2015
Location: EDT+12
Pronoun: He
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).
Last edited by BulletNLynchproof on Wed Jun 13, 2018 2:06 am, edited 1 time in total.
GTKAS - BNL (Updated, check it out!)
The Room Odds is in singups! 3/9 slots filled.
Pre-in for The Wise, Old Judge! 0/5 slots taken.

BulletNLynchproof
Mafia Scum

Joined: September 16, 2015
Location: EDT+12
Pronoun: He
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.
GTKAS - BNL (Updated, check it out!)
The Room Odds is in singups! 3/9 slots filled.
Pre-in for The Wise, Old Judge! 0/5 slots taken.

Who
Yes?

Joined: March 22, 2013
Location: Third Base
Pronoun: He
Nice proofs, you got it.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

Gosrir Elmer Odels
Goon

Joined: May 20, 2018
Pronoun: He
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
Mafia Scum

Joined: April 08, 2016
Pronoun: They
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.
"one of these days i'll read you correctly" - Transcend, Micro 714

StrangerCoug
Does not Compute

Joined: May 06, 2008
Location: El Paso, Texas
Pronoun: He
Never mind; I think I had too easy a question Let me think of a new one...
STRANGERCOUG: Stranger Than You!
Current avatar by PurryFurry of FurAffinity.

Want to take a survey for a Card Sharks game on the Mish Mash Discord server? Click here! (Survey changed September 15)

Inferno390
Mafia Scum

Joined: October 03, 2017
Location: With the Flying Pumpkin That Shoots Laser Beams Out Of It's Ass
Pronoun: He
In post 60, BTD6_maker wrote: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?
"Do I have permission to....refute some of the bs that Inferno just spewed out?"--TywinL
“Does anyone know if Inferno is prone to going of on huge tangents of twisted logic regarding basically alignment neutral posting? Asking for a friend ...”—MagnaofIllusion
Inferno390 GTKAS
Mafiascum Moderator Society

implosion

Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He
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
Yes?

Joined: March 22, 2013
Location: Third Base
Pronoun: He
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).
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

BTD6_maker
Mafia Scum

Joined: April 08, 2016
Pronoun: They
None of the circles are tangent to each other.
"one of these days i'll read you correctly" - Transcend, Micro 714

implosion

Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He
In post 64, Who wrote:
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
Yes?

Joined: March 22, 2013
Location: Third Base
Pronoun: He
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.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

implosion

Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He
You still have to do the last step that you did in your first solution, but yes.

BTD6_maker
Mafia Scum

Joined: April 08, 2016
Pronoun: They
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.
"one of these days i'll read you correctly" - Transcend, Micro 714

Previous
[ + ]