Math and Logic Puzzles: Redux

This forum is for playing games other than Mafia and Mafia variants.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Math and Logic Puzzles: Redux

Post Post #0 (isolation #0) » Wed Apr 18, 2018 6:52 pm

Post by implosion »

The old thread got archived. Here's a new one!

Vaguely, someone will post a math or logic puzzle. Other people try to solve it, and whoever solves it gets to post their own. But in practice, things can be free-formed; if you have an interesting riddle or puzzle, feel free to post it! Just don't flood the thread with a bunch of different things at once.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #1 (isolation #1) » Wed Apr 18, 2018 6:52 pm

Post by implosion »

First is one that I thought of a few days ago. Consider the following way to create a graph based on a finite string:

-For each possible permutation of the characters of the string, create a vertex of the graph labeled with that permutation.
-Create an edge between any two permutations with the property that there exists a contiguous substring of one that can be reversed to form the other.

For instance, if our string is "happy", then the vertices for "happy" and "hppay" would share an edge, because you can reverse the "app" substring; likewise, "happy" would be adjacent to "yppah", "ahppy", etc.

Must any graph formed in this way must be regular (with every vertex having the same degree)? Prove, or provide a counterexample.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #4 (isolation #2) » Thu Apr 19, 2018 8:09 am

Post by implosion »

That's pretty much it. The only other slight missing piece is showing that adding duplicate letters doesn't make any other reversals "not count," that is, that any reversal where the endpoints are distinct characters will never do the same thing as a different reversal where the endpoints are distinct characters, even if there are duplicate characters elsewhere in the string. But this isn't too difficult to show.

Here's one that's based on something that me and Mitillos and Ellibereth discussed in sitechat a while ago.

Suppose we have an undirected graph G, and a function f: G->R≥0. That is, we have a graph and each vertex is labeled with a nonnegative real number. Additionally, f fulfills one other property: for any vertex v in G, f(v) is the average of f(w) over all neighbors w of v. That is, each vertex's label is the average of its neighbors' labels. Call a graph G
balanceable
if there exists such a function f that is nonconstant.

1) Prove that no finite graph is balanceable.
2) Exhibit some balanceable graph and a nonconstant function f with the given property for it. Note that no vertex can have infinite degree, as that would break the definition.
3) (the original problem we looked at, and we never figured it out, but feel more than free to take a crack if you want to): consider the 2-d square lattice graph (put a vertex at every lattice point in the cartesian plane, then connect each vertex to the four adjacent vertices). Is this graph balanceable?
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #63 (isolation #3) » 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
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #66 (isolation #4) » 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
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #68 (isolation #5) » 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
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #122 (isolation #6) » Fri May 22, 2020 2:36 pm

Post by implosion »

Spoiler:
v is the value of the check, c is the number of cents actually received, d is the number of dollars actually received.

v = 100c + d
100d + c - 5 = 2v = 200c + 2d

98d - 199c = 5

Taking this mod 199, 98d is congruent to 5 mod 199, and 199 is prime so in the field of order 199 there's a unique solution here. 2*98 = 196 = -3, so 31 * 2 * 98 = 62 * 98 = -93. Thus, 63 * 98 = 5. So d = 63, and c = (98 * 63 - 5) / 199 = 31.

So the number of dollars actually received was 63, the number of cents was 31, and the value of the check was $31.63.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #123 (isolation #7) » Fri May 22, 2020 2:40 pm

Post by implosion »

In post 5, Ircher wrote:What exactly is a function in terms of a graph? As in, what inputs is it mapping? I may give this a try, but I would.need to know the previous.
Also, two years late, but I never answered this question on the first page!

A function on a graph typically means a function on the set of vertices. So that function maps each vertex to a nonnegative real number.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #154 (isolation #8) » Tue Dec 08, 2020 10:49 pm

Post by implosion »

I suspect it's 1/2 but am not confident and am intrigued to try to show it formally and will think about it more later
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #159 (isolation #9) » Wed Dec 09, 2020 8:18 am

Post by implosion »

In post 155, Sirius9121 wrote:
In post 154, implosion wrote:I suspect it's 1/2 but am not confident and am intrigued to try to show it formally and will think about it more later
please note that both requirements need to be fulfilled... its lower than 1/2
I understand, I came up with a heuristic argument that made me think it would be 1/2 anyway asymptotically. But it certainly wasn't rigorous or anything.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #184 (isolation #10) » Mon Feb 14, 2022 4:43 pm

Post by implosion »

337500/234966429149994773
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #187 (isolation #11) » Mon Feb 14, 2022 8:29 pm

Post by implosion »

1/72
100/1001
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #189 (isolation #12) » Mon Feb 14, 2022 8:34 pm

Post by implosion »

101 / 1001
100 / 1003
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #190 (isolation #13) » Mon Feb 14, 2022 8:36 pm

Post by implosion »

2 / 71
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #195 (isolation #14) » Mon Feb 14, 2022 9:26 pm

Post by implosion »

3 / 71
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #201 (isolation #15) » Tue Feb 15, 2022 7:12 am

Post by implosion »

Spoiler: Answer
p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.

In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #233 (isolation #16) » Mon Mar 20, 2023 7:55 pm

Post by implosion »

Spoiler:
I think the unspecified thing is who the first and last games are played against, and the answer being looked for here is "choose to play against the sister first"?

Assuming your probability of winning against the sister is p and the brother is q, there's some inductive argument for calculating an exact probability of winning 2 in a row, and that could be easily used to show that it's better to choose to play the sister first when p < q. But based on the phrasing, it should be easier to just assume p is very small and q is very large, so losing a game to the brother is a rare event (even among samples where we win a game against the sister, which is also a rare event, as the two are independent), so having more chances to win against the sister will maximize your probability of winning.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14335
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #276 (isolation #17) » Sat Apr 29, 2023 6:46 am

Post by implosion »

Spoiler:
So then at each step, pick a neck to chop from that is at the highest level from the root possible, and among such heads, choose one that has the highest number of sibling heads (heads that extend from the same immediate root as it). Chopping a head at level l with s siblings will always reduce the number of s-sibling l-level roots by 1 because the replication can make (s-1)-sibling l-level roots by copying that part of the tree, but can't make anything else at level l or higher because the replication signal goes downward. Eventually all s-sibling l-level roots will be gone, and next are all the (still finitely many) (s-1)-sibling l-level roots, and so on until everything at level l is gone, etc. At each step more future work will appear but nothing that's already been dealt with can spring up again. You can't put an a priori bound on how long it'll take unless you can put an a priori bound on how many times a tree might replicate (which you don't need to do), but every step is guaranteed to make forward progress at its given (s, l) ordered pair, there are only ever finitely many such ordered pairs to deal with (because each replication is finite), and so each such ordered pair will take finite time to deal with.

In fact I
think
this can be turned into an even stronger conjecture, which is that actually
any
order that HyperErcules cuts the heads will eventually kill the hydra, even if he tries not to.The argument would be similar, that making a cut anywhere makes progress on that (s, l) subproblem, meaning that
eventually
you'll solve the (s, l) subproblem and everything below it, which will force you to make a cut at a higher (s, l) subproblem and make progress there. So eventually you'll have to make "actual" progress by cutting at the highest level problem.
Post Reply

Return to “The Whole Sort of General Mish Mash”