Math and Logic Puzzles: Redux

[Gosrir Elmer Odels]

Suppose I have a fence with n spikes. For example:

Code: Select all

    /¤\       /¤\   
   /   \     /   \  
  /     \   /     \ 
¤/       \¤/       \¤
|         |         |
|         |         |
|         |         |

The fence above has 2 spikes. The ¤'s represent marbles that are there for decoration, but currently they're all green! (as you can see) So I want to paint some of them red, to improve the looks. But there is a problem: something is wrong with the paint, so whenever I paint a marble on the top red, the paint runs down to the two marbles below, & colours those red too.

How many patterns are possible if my fence has n spikes?

(Example: for n=1 there are 5 patterns: all green; bottom left red; bottom right red; both at the bottom red; or all red.)

(Disclaimer: I intentionally tried to avoid very formal mathematical language while formulating this question.)

[Gosrir Elmer Odels]

Yes! You're a bit off with the indices, since a_1=5=f_4, a_2=13=f_6, so in general a_i=f_{2i+2}, but aside from that your solution is correct.

(In the hypothetical k=0 case you'd still have one marble, which you can either colour or not, so a_0=2.)

[Gosrir Elmer Odels]

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?

[Gosrir Elmer Odels]

Exactly, very well-put.

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

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

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

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