These are some math/coding problems and research questions (probably already solved by someone) that I thought of <edit>LIKE 10+ YEARS AGO WHEN I WAS EVEN STUPIDER</edit>. They're in no particular order. Let me know if you have solutions to any of them!
Let S be an infinite set.
A round-robin tournament schedule for n teams specifies a set of rounds consisting of (two-team) matches in such a way that every possible match occurs exactly once and no team has more than one match in the same round. (That is, it's a partition of Kn's edge set into matchings.) A perfect schedule is one that uses only n-1 rounds (each with n/2 matches).
You need to perform a security upgrade on each tower in a communications network. A tower can only be upgraded while it and all neighboring towers are occupied by technicians. A technician can remain inside a tower after upgrading it (in order to enable upgrades of adjacent towers) but can't re-enter an upgraded tower after leaving it.
Let X1, X2, ... be an infinite sequence of independent, identically-distributed continuous random variables, and let Z = ∑n 2-n 1Xn < Xn+1.
You shuffle an n-card deck and deal k cards to magician A. He looks at them and begins placing them face up onto the table (in an order of his choosing) until only one remains in his hand. To your amazement, magician B is able to name this last card without seeing it. After many repetitions, you are convinced that the magicians can do this regardless of the cards you give them. If this is the case, we call their strategy an (n, k) card trick.
You are playing a difficult verison of Battleship: The sea is an infinite plane, and each of the enemy's 100 ships occupies a single point and can teleport each night. Each ship's movement is controlled by an unknown deterministic computer program whose output gives the ship's coordinates for each day. The coordinates can be any definable real numbers and are supplied by the navigation program to the teleportation system in the form of their defining formulae. Each day, you may bomb a single point in the plane (by providing a pair of defining formulae to the artillery); to sink a ship requires 10 direct hits on 10 consecutive days. You recieve no information (e.g. about the success of your bombings or the movement of ships) until the entire enemy navy has been eliminated.
Let D be the number of distinct values taken by n independent geometric random variables.
Is the problem of determining whether a given lambda expression represents a Church numeral decidable?
Define K(n) as the largest number whose Church numeral can be written in n or fewer characters of klambda.
Define k(n) as the smallest number whose Church numeral can not be written in n or fewer characters of klambda.
Given two strings P and T (thinking of them as pattern and text, respectively), we say that P accepts T if there is a function f from characters to strings such that f(P[0]) + f(P[1]) + f(P[2]) + ... = T. For example, "aabb" accepts "catcatdogdog" via the function {a↦"cat", b↦"dog"}. We allow the empty string "" as a value of f, so "aaab" accepts "horse" via the map {a↦"", b↦"horse"}. If P accepts T via a function without empty-string values, we say that P properly accepts T.
The pattern-similarity of two nonempty strings X and Y is the length of the longest pattern that properly accepts both X and Y.
We say that two strings P and Q represent the same pattern if they accept exactly the same set of strings.
Define a pattern chain as a sequence of strings in which each string accepts the next one and no two strings represent the same pattern.
Note that if we think of strings as elements of a free monoid S, then "P accepts T" is equivalent to "There is a homomorphism f:S→S for which f(P)=T". This suggests a way to generalize "accepts" to a relation on any algebraic structure A, defined by: x RA y iff there is a homomorphism f:A→A for which f(x)=y. For example, if A is the monoid of nonnegative integers under addition, then RA turns out to be the relation of divisibility.
A directed acyclic graph G with vertices labeled 1 through 100 is constructed by placing an edge from i to j with probability p for each 1 ≤ i < j ≤ 100 (independently).
Define G' as the undirected graph with the same edges as G. G' is a tree if it is connected and has no cycles.
Magma-related definitions:
Problems:
We say that a finite subset of ℕd is supported if it is a union of blocks of the form {1, ..., x1}×{1, ..., x2}×...×{1, ..., xd}. This is equivalent to being downward closed with respect to the coordinatewise partial order.
Define fd(n) as the number of supported subsets of ℕd with exactly n elements. Note that f2 is the integer partition function, because the size-n supported sets in 2D are the Young diagrams of partitions of n.
Let gd(n) count the supported sets of size n, ignoring "copies" that can be obtained by relabeling the coordinate axes. (Formally: Let the symmetric group Sd act on ℕd by permuting element coordinates, and thus on ℘(ℕd) elementwise. Note that this action can be restricted to the class of supported sets; define gd(n) as the resulting number of orbits.)
Prove that for d≥n-1, gd(n) = gn-1(n). Define h(n) as this value.
A corner set is a finite antichain in ℕd with respect to the coordinatewise partial order.
The maximal elements of a supported set S form a corner set (consisting of the "upper corner" of each block in S's shortest representation as a union of blocks), and the downward closure of a corner set C is a supported set (i.e. the union of the blocks whose "upper corners" are the elements of C). Via these inverse operations, the supported sets are in one-to-one correspondence with the corner sets. Counting the corner sets of a given size amounts to counting the supported sets of a given "complexity".
There are infinitely many corner sets of any given size, so to count corner set structures by number of elements, we need to require some kind of "compactness". We will say that a set is compacted if it doesn't "skip" values in any dimension. That is, C ⊂ ℕd is compacted if for each i ∈ {1, ..., d}, the set {xi | x ∈ C} has the form {1, ..., mi} for some mi.
Every finite subset of ℕd has a unique "compacted version", i.e. a bijection to a compacted set that preserves the relative order of its elements in each dimension. This order information fully describes the compacted set; an equivalent definition of "compacted set" is a list of d total preorders on an arbitrary finite set. Note that the compacted version of a corner set is still a corner set.
Define functions F and G analagously to f and g above, counting compacted corner sets instead of supported sets. Find an analagous version of the fact justifying h's definition and define H accordingly.
For a directed graph G=(V, E), define R(G) as the relation on V of reachability in G. By replacing E with its transitive reduction E', we obtain the smallest graph G'=(V, E') for which R(G') = R(G).
However, if the goal is just to find a small graph that imposes the same reachability relation on V that G does, we might be able to do better than this by adding "dummy vertices". For example, the "complete bipartite DAG" (V=V1+V2, E=V1×V2), with Ω(V2) edges, is not reduced by transitive reduction, but we can add a single extra vertex and rearrange edges to obtain the O(V) representation (V'=V1+{x}+V2, E'=(V1×{x})+({x}×V2)), in which every vertex in V2 is still reachable from every vertex in V1.
Define T(G) as the minimum value of |E'| over all graphs G'=(V', E') that satisfy V ⊆ V' and R(G') ∩ V×V = R(G).
Define f(n) as the maximum value of T over all directed graphs with n vertices.
Let S be a finite subset of the interval [0, 1) and k a positive integer. We say that S is k-divisible if each of the subintervals [i/k, (i+1)/k) (for 0 ≤ i < k) contains the same number of points from S. For example, {0.1, 0.4, 0.8} is k-divisible only for k=1 and k=3.