Math and Logic Puzzles: Redux

[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.

[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.

[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?

[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.

[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.

[implosion]

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

[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.

[implosion]

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.

[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

[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

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.

[implosion]

337500/234966429149994773

[implosion]

1/72
100/1001

[implosion]

101 / 1001
100 / 1003

[implosion]

2 / 71

[implosion]

3 / 71

[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.