When is Tutte’s theorem in K₅ violated?

Theorem

A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V − U has at most |U| connected components with an odd number of vertices.
Tutte’s theorem

Illustration
tutte_theorem_examples
Figure 1. Tutte theorem examples

Consider the two examples given in Figure 1. G is a bipartite graph and we consider two possible subsets U the induced subgraph of G-U is given on the right side.

  1. For U₁ the number of odd components in G-U is 1 and the size of U is given with 3. Because 1 ≤ 3, the Tutte theorem holds.
  2. For U₂ the number of odd components in G-U is also 1 and the size of U is also given with 3. Again, the Tutte theorem holds.

For any U, this condition will hold. Underneath the perfect matching is given (vertex 1 is associated to vertex 2, etc).

Problem setting

planar graph K5

Figure 2. Planar graph K5 and a reduced variant

Consider graph K₅. A perfect matching clearly cannot exist for K₅, because a perfect matching can only exist if the number of vertices is even (as every vertex is associated to another vertex). Because the Tutte theorem provides a necessary and sufficient condition for the existence of a perfect matching, it should yield

For some subset U of V, the subgraph induced by V − U
has less than |U| connected components with an odd number of vertices.

Question

What is U for K₅? The solution is equivalent for its incomplete variant, which was originally given to me.

Solution

I wasn’t able to come up with a solution. So I wrote a program to try all combinations:

#!/usr/bin/env python3

import itertools

def component_sizes(G):
    """component sizes in an undirected graph"""
    comps = list(set([v]) for v in G[0])
    for e in G[1]:
        s, t = e[0], e[1]
        idx_s, idx_t = -1, -1
        for i, comp in enumerate(comps):
            if s in comp:
                idx_s = i
            if t in comp:
                idx_t = i
        if idx_s == idx_t:
            continue
        else:
            for item in comps[idx_t]:
                comps[idx_s].add(item)
            comps.remove(comps[idx_t])
    return tuple(sorted(len(comp) for comp in comps))

assert component_sizes(([1], [])) == (1,)
assert component_sizes(([1, 2], [])) == (1, 1)
assert component_sizes(([1, 2], [(1, 2)])) == (2,)
assert component_sizes(([1, 2, 3], [(1, 2)])) == (1, 2)

def subgraph(G, excl_vs):
    """Subgraph induces by excluding vertices"""
    red_V = tuple(filter(lambda v: v not in excl_vs, G[0]))
    red_E = tuple(filter(lambda e: e[0] not in excl_vs and e[1] not in excl_vs, G[1]))
    return (red_V, red_E)

assert subgraph(([1], []), [1]) == (tuple(), tuple())
assert subgraph(([1, 2], [(1, 2)]), [1]) == ((2,), tuple())
assert subgraph(([1, 2, 3], [(1, 2), (2, 3), (3, 1)]), [1]) == ((2, 3), ((2, 3),))

if __name__ == '__main__':
    def excl_vs_selection(G):
        for size in range(len(G[0])):
            for sel in itertools.combinations(G[0], r=size):
                yield set(sel)

    K5 = ((1, 2, 3, 4, 5), list(itertools.combinations(range(1,6), r=2)))
    reduced_K5 = ((1, 2, 3, 4, 5), [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

    G = K5
    for excl_vs in excl_vs_selection(G):
        sub = subgraph(G, excl_vs)
        sizes = component_sizes(sub)
        odd_sized_comps = len(list(map(lambda v: v % 2 == 0, sizes)))
        if odd_sized_comps > len(excl_vs):
            print(excl_vs)
            #raise ValueError("Tutte theorem violated with exclusion vertices {}".format(excl_vs))

The program yields set(). Hence the only solution is the empty set.

Consider U = {}. Then the induced graph is K₅ itself. The number of connected components in K₅ is 1 (all pairs of vertices are reachable from each other) and this component has an odd number of vertices (namely 5). The size of U is 0. And 1 > 0, so the Tutte theorem is violated and no perfect matching exists indeed.

When is Tutte’s theorem in K₅ violated?

Make 24 out of 1, 3, 4 and 6

Problem

Give a mathematical expression which equals 24. This expression is only allowed to use the basic arithmetic operators +, -, * and /. The numbers 1, 3, 4 and 6 must occur exactly once. No magic or tricks!

Setting

I was given this problem last Friday by one colleague. It was ridiculously difficult to come up with a solution. As mathematician you try to understand the structure behind the problem. You look at the prime numbers involved. In the expression you have {3, 2, 2, 2, 3} and in 24 you have {2, 2, 2, 3}. So you need to get rid of one three. But how? None of us 6 guys came up with a solution in less than an hour. But we actually found one academic who found the solution after 2 hours (a bit of sleep was involved, because he was very tired).

Well, my mathematical brain failed, but my computer science brain screamed “brute force!”. So let’s do it. I wrote a python script, which solved a subproblem in 18 lines. This is a more complete version which solves the problem for any four numbers and any target value. This script prints possible correct solutions to stdout in less than 0.5 seconds:

import itertools

def parenthesized(a, b, c, d):
    """Generate all expressions where operators
    are represented with substitution characters
    """
    yield '((`{} $ <{}) @ (>{} ! _{}))'.format(a, b, c, d)
    yield '((`{} $ (<{} @ >{})) ! _{})'.format(a, b, c, d)
    yield '(`{} $ ((<{} @ >{}) ! _{}))'.format(a, b, c, d)
    yield '(`{} $ (<{} @ (>{} ! _{})))'.format(a, b, c, d)

def main():
    """Main routine generating math expressions equating 24
    using numbers {1, 3, 4, 6} exactly once and using operators
    -, +, / or *.
    """
    for arr in itertools.permutations([1, 3, 4, 6]):
        for expr in parenthesized(*arr):
            # we can omit '-' in these iterations, because all values
            # will also be considered with a sign
            for fo, so, to in itertools.product(['+', '/', '*'], repeat=3):
                for s1, s2, s3, s4 in itertools.product(['', '-'], repeat=4):
                    try:
                        # replace operators
                        e = expr.replace('$', fo).replace('@', so).replace('!', to)
                        # use either sign '' (hence +) or '-' (hence -) at every place
                        e = e.replace('`', s1).replace('<', s2).replace('>', s3).replace('_', s4)
                        result = eval(e)
                    except ZeroDivisionError:
                        continue
                    if result == 24:
                        yield e

if __name__ == '__main__':
    for solution_expression in main():
        print(solution_expression)
Spoiler

In the following I will give a list of hints. The further below you go, the closer you come to the solution (select text to display items). The solution itself is not given here:

  1. Most values we ended up with are too small for 24. So we conjectured that number 6 will occur as factor, which turned out to be true.
  2. Factor 6? So we look for factor 4 as well, right? Actually no. I mean yes, but with an indirect representation.
  3. Given {1, 4} on the left-hand side and {1, 3, 4} on the right-hand side. Find operators such that LHS and RHS equate.
  4. How about 1 / (1 / 4)? Two ones? I guess one of them has to be 6.
  5. Given 6 / (1 / 4)? How can we represent 1/4 using {1, 3, 4}?
Make 24 out of 1, 3, 4 and 6

Mapping lexicographical comparison to integer comparison

Claim

(a, b) < (c, d) with a,b,c,d ∈ [0,M) ⇔ a · M + b < c · M + d
(a, b) = (c, d) with a,b,c,d ∈ [0,M) ⇔ a · M + b = c · M + d
(a, b) > (c, d) with a,b,c,d ∈ [0,M) ⇔ a · M + b > c · M + d

Proof by case distinction
relation to prove constraint evaluation conclusion
(a, b) < (c, d) a < c a · M + M – 1 < c · M
(a, b) < (c, d) a = c ∧ b < d a · M + b < c · M + d 0 + b < 0 + d ✓
(a, b) = (c, d) a = c ∧ b = d a · M + b = c · M + d 0 + 0 = 0 + 0 ✓
(a, b) > (c, d) a = c ∧ b > d a · M + b > c · M + d 0 + b > 0 + d ✓
(a, b) > (c, d) a > c a · M > c · M + M – 1
Rationale

This just exploits the nature of a lexicographical order itself for bounded domains. Consider two binary numbers and they get compared. This integer comparison equals the lexicographical tuple comparison of its digit expansion. I just wanted to make this explicit as my head was screwing around with it.

Mapping lexicographical comparison to integer comparison

no actual ‘creative’ work

I just found that in the TU Graz newsgroup and I think it is worth sharing to the general public.
I am censoring his name, because I don’t want to associate him with the quote he apologized for (as stated below).

> It is about allowing “intense discussion” with another person, without
> fearing to get accused of “cheating” afterwards. What else would be
> the reason for group work in such a case!? Discussing your solution
> line by line with another person can help learning. That’s what the
> teacher is aiming for (I assume).

As far as I know the thing we’re talking about is simply mathematics,
no programming or actual ‘creative’ work so far.
The results, and most likely also the steps to come there, will be the
same for everyone.

Maria points out an awkwardness of this followup:

On 2015-03-26 11:32, {CENSORED} wrote:
> …simply mathematics…

> …no actual ‘creative’ work…

ymmd

Maria

YMMD too 😉 His followup:

Ouch :’-(
Now even though this is the flames ng I’m still sorry about that.
I hope it does not hurt that bad in the context it was written in :\

no actual ‘creative’ work

A complete, binary tree always has 2^n-1 vertices. Why -1?

Thinking about a problem, I came across the following basic graph-theoretical question:

Given is a complete, binary tree G(V, E). The cardinality of V always needs be constructed with
V=2n1

with n being an element of natural numbers excluding zero. Where does the minus 1 come from?

Graph Theorem
Examples for relation between number of vertices and 2^n-1

The solution lies in the logarithmically structure of the tree. The height of a complete, binary tree corresponds to
log2(V)

. Therefore firstly, the number of vertices can be described with
i=0d2i

where d is the depth of the tree and
20

adds the additional 1. Secondly, if we look at the table with logarithmic values, we can see that 2 instead of 1 is the first parameter to return 1.

i log2(i)
1 0.0
2 1.0
3 1.58496250072
4 2.0
5 2.32192809489
6 2.58496250072
7 2.80735492206
8 3.0
9 3.16992500144

Thanks, credit goes to Felix for the clue 🙂

Note. This blog post uses MathML supported by any HTML5 web browser natively. WordPress obviously does not. It inserts stupid line breaks before <math>.

A complete, binary tree always has 2^n-1 vertices. Why -1?

Lösung: Welche Zahl fehlt?

… also 229, erhält man eine neunstellige Zahl. Diese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, …, 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das?

>>> a = str(2**29)
>>> b = dict(zip(range(0,10), (True,)*10))
>>> for i in a:
...     b[int(i)] = False
... 
>>> b
{0: False, 1: False, 2: False, 3: False, 4: True, 
5: False, 6: False, 7: False, 8: False, 9: False}
>>> 2**29
536870912
>>> 

Ich hatte eigentlich erwartet, dass 229 größer ist und bin deshalb vorsichtig geworden (habe wohl “neunstellig” überlesen). Aber Sven hat Recht: In C hätte ich auch mit modulo gearbeitet 🙂

via kubieziel

Lösung: Welche Zahl fehlt?

Euclidean algorithm

euklid_matura

Gestern implementierte ich den Euklidischen Algorithmus (rekursive, moderne Version) bei der Matura. Am Papier schrieb ich ihn nieder, weil ich ihn live programmieren wollte und vorher testete, aber letztendlich hatten wir für alles viel zu wenig Zeit.

euklid

Heute ist der euklidische Algorithmus Artikel des Tages beim englischen Wikipedia.

Python-Implementierungen für alle 4 Versionen verfügbar bei den cryptotools

Euclidean algorithm

Wieder mal ein Mathematikrätsel gelöst…

Manche meiner Mathe-Rätsel konnte ich selber lösen. Manche nicht. Ein Mathematikrätsel ist heute unabsichtlich mit einem neuen Datum versehen worden (*grml* WP) und Frederic hat eine Diskussion entfacht. Eine Skype-Konversation später haben wir die Lösung gefunden.

Der Kern des Problems:
2*0 = 1*0. In dem Problem wurde sozusagen durch 0 dividiert und das Ergebnis ist 2 = 1. Man könnte es mit x=1 anschreiben und dann sieht man es schön:

1 - 1 = 1 - 1
(1 + 1)(1 - 1) = 1(1 - 1)
2 * 0 = 1 * 0
2 = 1

Wo der Fehler auftritt:
(x + x)(x - x) ist als x2 + (x2 - x2) - x2 aufzulösen. Der hier geklammerte Ausdruck ist gleich null. Das ist jener Wert um den die linke Seite reicher ist als die rechte. Wenn man vorhin durch (x - x) dividiert, dividiert man eigentlich durch null. Die binomische Formel versteckt den Kern des Problems nur ein bisschen und verschleiert die Lösung. Es merkt gar nicht, wie man eigentlich eine Null heraushebt.

Ein äquivalentes Beispiel

3x2 - 3x2 = 3x2 - 3x2
3(x + x)(x - x) = 3x(x - x)
3x(1 + 1)(1 - 1) = 3x2(1 - 1)
3x(1 + 1)(0) = 3x2(0)
3x(1 + 1) = 3x2
6x = 3x2
Wieder mal ein Mathematikrätsel gelöst…

2 Matherätsel

Wurde mal wieder Zeit. Das erste Rätsel entstammt aus meinem Spezialgebiet Komplexe Zahlen (j = √-1, j2 = -1):

Wo liegt der Fehler?

1 = √1 = √-1 * √-1 = √(-1*-1) = √-1

Lösung

Das zweite Rätsel kann man mit dem chinesischen Restsatz lösen. Hat also mit meinem Spezialthema Kryptologie was zu tun. Anders auch noch?

Eine Bande von 17 Räubern stahl einen Sack mit Goldstücken. Als sie ihre Beute teilen wollten, blieben 3 Goldstücke übrig. Beim Streit darüber, wer ein Goldstück mehr erhalten sollte, wurde 1 Räuber erschlagen. Jetzt blieben bei der Verteilung 10 Goldstücke übrig. Erneut kam es zu Streit und wieder verlor ein Räuber sein Leben. Jetzt ließ sich die Beute gleichmäßig verteilen. Wieviele Goldstücke waren mindestens im Sack?

via Hallo Welt für Fortgeschrittene

2 Matherätsel