Math and Logic Puzzles: Redux

This forum is for playing games other than Mafia and Mafia variants.
Felissan
Goon
 
User avatar
Joined: April 03, 2015
Location: France
Pronoun: She

Post Post #50  (ISO)  » Tue May 29, 2018 5:46 pm

Spoiler: My answer
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
"Also, the me in your signature just made the me in this thread lose the game and I'm not sure how to feel about this." - DeathRowKitty 2018

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

Gosrir Elmer Odels
Goon
 
User avatar
Joined: May 20, 2018
Pronoun: He

Post Post #51  (ISO)  » Wed May 30, 2018 2:00 am

Exactly, very well-put. :)

Gosrir Elmer Odels
Goon
 
User avatar
Joined: May 20, 2018
Pronoun: He

Post Post #52  (ISO)  » Thu May 31, 2018 2:55 am

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

Post Post #53  (ISO)  » Thu May 31, 2018 7:29 am

Okay, I think I have a solution. The square lattice cannot be balanced.
Spoiler: "Here's what I did. It's not nice."
abc
def
ghi


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?
 
User avatar
Joined: March 22, 2013
Location: Third Base
Pronoun: He

Post Post #54  (ISO)  » Wed Jun 13, 2018 1:37 am

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?
 
User avatar
Joined: March 22, 2013
Location: Third Base
Pronoun: He

Post Post #55  (ISO)  » Wed Jun 13, 2018 1:43 am

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
 
User avatar
Joined: September 16, 2015
Location: EDT+12
Pronoun: He

Post Post #56  (ISO)  » Wed Jun 13, 2018 2:01 am

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
 
User avatar
Joined: September 16, 2015
Location: EDT+12
Pronoun: He

Post Post #57  (ISO)  » Wed Jun 13, 2018 2:06 am

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?
 
User avatar
Joined: March 22, 2013
Location: Third Base
Pronoun: He

Post Post #58  (ISO)  » Wed Jun 13, 2018 2:14 am

Nice proofs, you got it.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
1

Gosrir Elmer Odels
Goon
 
User avatar
Joined: May 20, 2018
Pronoun: He

Post Post #59  (ISO)  » Wed Jun 13, 2018 12:31 pm

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
 
User avatar
Joined: April 08, 2016
Pronoun: They

Post Post #60  (ISO)  » Wed Jun 13, 2018 1:58 pm

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
 
User avatar
Joined: May 06, 2008
Location: El Paso, Texas
Pronoun: He

Post Post #61  (ISO)  » Fri Jun 29, 2018 1:00 pm

Never mind; I think I had too easy a question :P 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
 
User avatar
Joined: October 03, 2017
Location: With the Flying Pumpkin That Shoots Laser Beams Out Of It's Ass
Pronoun: He

Post Post #62  (ISO)  » Tue Jul 03, 2018 8:25 pm

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
Jack of All Trades
 
User avatar
Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He

Post Post #63  (ISO)  » Tue Jul 03, 2018 8:35 pm

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?
 
User avatar
Joined: March 22, 2013
Location: Third Base
Pronoun: He

Post Post #64  (ISO)  » Tue Jul 03, 2018 10:10 pm

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
 
User avatar
Joined: April 08, 2016
Pronoun: They

Post Post #65  (ISO)  » Tue Jul 03, 2018 11:38 pm

None of the circles are tangent to each other.
"one of these days i'll read you correctly" - Transcend, Micro 714

implosion
Jack of All Trades
 
User avatar
Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He

Post Post #66  (ISO)  » Wed Jul 04, 2018 12:03 am

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?
 
User avatar
Joined: March 22, 2013
Location: Third Base
Pronoun: He

Post Post #67  (ISO)  » Thu Jul 19, 2018 5:49 pm

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
Jack of All Trades
 
User avatar
Joined: September 09, 2010
Location: zoraster's back yard
Pronoun: He

Post Post #68  (ISO)  » Thu Jul 19, 2018 6:01 pm

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

BTD6_maker
Mafia Scum
 
User avatar
Joined: April 08, 2016
Pronoun: They

Post Post #69  (ISO)  » Sat Sep 29, 2018 3:18 am

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
[ + ]

Return to The Whole Sort of General Mish Mash