Math and Logic Puzzles: Redux

This forum is for playing games other than Mafia and Mafia variants.
User avatar
Felissan
Felissan
Goon
User avatar
User avatar
Felissan
Goon
Goon
Posts: 216
Joined: April 3, 2015
Location: France

Post Post #50 (ISO) » Tue May 29, 2018 11:46 am

Post by Felissan »

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
"You've made me make myself lose the game so many times that I feel like it's an entirely new game I'm losing"
- DeathRowKitty 2022
User avatar
Gosrir Elmer Odels
Gosrir Elmer Odels
Goon
User avatar
User avatar
Gosrir Elmer Odels
Goon
Goon
Posts: 135
Joined: May 19, 2018

Post Post #51 (ISO) » Tue May 29, 2018 8:00 pm

Post by Gosrir Elmer Odels »

Exactly, very well-put. :)
User avatar
Gosrir Elmer Odels
Gosrir Elmer Odels
Goon
User avatar
User avatar
Gosrir Elmer Odels
Goon
Goon
Posts: 135
Joined: May 19, 2018

Post Post #52 (ISO) » Wed May 30, 2018 8:55 pm

Post by 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.
User avatar
Gosrir Elmer Odels
Gosrir Elmer Odels
Goon
User avatar
User avatar
Gosrir Elmer Odels
Goon
Goon
Posts: 135
Joined: May 19, 2018

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

Post by 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.
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.)
User avatar
Who
Who
Yes?
User avatar
User avatar
Who
Yes?
Yes?
Posts: 4745
Joined: March 22, 2013
Location: Third Base

Post Post #54 (ISO) » Tue Jun 12, 2018 7:37 pm

Post by Who »

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 Tue Jun 12, 2018 7:44 pm, edited 1 time in total.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
6
User avatar
Who
Who
Yes?
User avatar
User avatar
Who
Yes?
Yes?
Posts: 4745
Joined: March 22, 2013
Location: Third Base

Post Post #55 (ISO) » Tue Jun 12, 2018 7:43 pm

Post by 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.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
6
User avatar
BNL
BNL
Micro Madness
User avatar
User avatar
BNL
Micro Madness
Micro Madness
Posts: 3338
Joined: September 15, 2015
Location: EDT+12

Post Post #56 (ISO) » Tue Jun 12, 2018 8:01 pm

Post by 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).
Last edited by BNL on Tue Jun 12, 2018 8:06 pm, edited 1 time in total.
GTKAS - BNL

Busy, on indefinite V/LA. May return April 2020
User avatar
BNL
BNL
Micro Madness
User avatar
User avatar
BNL
Micro Madness
Micro Madness
Posts: 3338
Joined: September 15, 2015
Location: EDT+12

Post Post #57 (ISO) » Tue Jun 12, 2018 8:06 pm

Post by 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.
GTKAS - BNL

Busy, on indefinite V/LA. May return April 2020
User avatar
Who
Who
Yes?
User avatar
User avatar
Who
Yes?
Yes?
Posts: 4745
Joined: March 22, 2013
Location: Third Base

Post Post #58 (ISO) » Tue Jun 12, 2018 8:14 pm

Post by Who »

Nice proofs, you got it.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
6
User avatar
Gosrir Elmer Odels
Gosrir Elmer Odels
Goon
User avatar
User avatar
Gosrir Elmer Odels
Goon
Goon
Posts: 135
Joined: May 19, 2018

Post Post #59 (ISO) » Wed Jun 13, 2018 6:31 am

Post by 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.
User avatar
BTD6_maker
BTD6_maker
Mafia Scum
User avatar
User avatar
BTD6_maker
Mafia Scum
Mafia Scum
Posts: 2244
Joined: April 7, 2016

Post Post #60 (ISO) » Wed Jun 13, 2018 7:58 am

Post by 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.
"one of these days i'll read you correctly" - Transcend, Micro 714
User avatar
StrangerCoug
StrangerCoug
He/Him
Does not Compute
User avatar
User avatar
StrangerCoug
He/Him
Does not Compute
Does not Compute
Posts: 12457
Joined: May 6, 2008
Pronoun: He/Him
Location: San Antonio, Texas
Contact:

Post Post #61 (ISO) » Fri Jun 29, 2018 7:00 am

Post by StrangerCoug »

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.
User avatar
Inferno390
Inferno390
Mafia Scum
User avatar
User avatar
Inferno390
Mafia Scum
Mafia Scum
Posts: 2190
Joined: October 3, 2017
Location: With the Flying Pumpkin That Shoots Laser Beams Out Of It's Ass

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

Post by Inferno390 »

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
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14328
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

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

Post by 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.
User avatar
Who
Who
Yes?
User avatar
User avatar
Who
Yes?
Yes?
Posts: 4745
Joined: March 22, 2013
Location: Third Base

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

Post by 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).
Who said that?
Chamber. It's all a conspiracy.
Or is it?
6
User avatar
BTD6_maker
BTD6_maker
Mafia Scum
User avatar
User avatar
BTD6_maker
Mafia Scum
Mafia Scum
Posts: 2244
Joined: April 7, 2016

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

Post by BTD6_maker »

None of the circles are tangent to each other.
"one of these days i'll read you correctly" - Transcend, Micro 714
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14328
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #66 (ISO) » Tue Jul 03, 2018 6:03 pm

Post by implosion »

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.
User avatar
Who
Who
Yes?
User avatar
User avatar
Who
Yes?
Yes?
Posts: 4745
Joined: March 22, 2013
Location: Third Base

Post Post #67 (ISO) » Thu Jul 19, 2018 11:49 am

Post by 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.
Who said that?
Chamber. It's all a conspiracy.
Or is it?
6
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14328
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

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

Post by implosion »

You still have to do the last step that you did in your first solution, but yes.
User avatar
BTD6_maker
BTD6_maker
Mafia Scum
User avatar
User avatar
BTD6_maker
Mafia Scum
Mafia Scum
Posts: 2244
Joined: April 7, 2016

Post Post #69 (ISO) » Fri Sep 28, 2018 9:18 pm

Post by 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.
"one of these days i'll read you correctly" - Transcend, Micro 714
Tazaro
Tazaro
Selfie
Tazaro
Selfie
Selfie
Posts: 3997
Joined: July 4, 2010
Location: I can go now without writing more

Post Post #70 (ISO) » Fri Jul 26, 2019 5:56 am

Post by 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.
Last edited by Tazaro on Fri Jul 26, 2019 6:45 am, edited 1 time in total.
Show
Maybe Subservience to Protocol isn't tantamount to Solution to Problem ...
"A little bit of yourself goes a long way"
Blue paint strokes of sadness that leave a trace of meaningfulness
Tell me, O Karen,
Do you feel better
After getting your pound of flesh?
User avatar
Kagami
Kagami
Jack of All Trades
User avatar
User avatar
Kagami
Jack of All Trades
Jack of All Trades
Posts: 7065
Joined: November 5, 2013

Post Post #71 (ISO) » Fri Jul 26, 2019 6:41 am

Post by Kagami »

puzzle!
155619367777177344298579121640577930358466048997080741489502115154736052423438639656322566701951512888971130859442675019505459646950828457775128

divided by

814295694336200301695257325143637445297122644140195688542610298982742658367669506161728178242191616818890832959609127053599963426497407079941861



Answer is nine letters and the name of a San Francisco based company.
User avatar
Kagami
Kagami
Jack of All Trades
User avatar
User avatar
Kagami
Jack of All Trades
Jack of All Trades
Posts: 7065
Joined: November 5, 2013

Post Post #72 (ISO) » Fri Jul 26, 2019 7:24 am

Post by Kagami »

With regard to , 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.
User avatar
geometry
geometry
Goon
User avatar
User avatar
geometry
Goon
Goon
Posts: 506
Joined: July 9, 2019
Location: outted chennisden alt

Post Post #73 (ISO) » Fri Jul 26, 2019 7:40 am

Post by geometry »

In post 63, implosion wrote: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!
I signed up to play
MAFIA
, not so you could roll me town again.
User avatar
geometry
geometry
Goon
User avatar
User avatar
geometry
Goon
Goon
Posts: 506
Joined: July 9, 2019
Location: outted chennisden alt

Post Post #74 (ISO) » Fri Jul 26, 2019 7:41 am

Post by geometry »

In post 49, Gosrir Elmer Odels wrote: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?
I signed up to play
MAFIA
, not so you could roll me town again.
Post Reply

Return to “The Whole Sort of General Mish Mash”