UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

Non-uniform beams and stiff strings isospectral to axially loaded uniform beams and piano strings

In this paper, we derive analytical expressions for mass and stiffness functions of transversely vibrating clamped-clamped non-uniform beams under no axial loads, which are isospectral to a given uniform axially loaded beam. Examples of such axially loaded beams are beam columns (compressive axial load) and piano strings (tensile axial load). The Barcilon-Gottlieb transformation is invoked to transform the non-uniform beam equation into the axially loaded uniform beam equation. The coupled ODEs involved in this transformation are solved for two specific cases (pq (z) = k (0) and q = q (0)), and analytical solutions for mass and stiffness are obtained. Examples of beams having a rectangular cross section are shown as a practical application of the analysis. Some non-uniform beams are found whose frequencies are known exactly since uniform axially loaded beams with clamped ends have closed-form solutions. In addition, we show that the tension required in a stiff piano string with hinged ends can be adjusted by changing the mass and stiffness functions of a stiff string, retaining its natural frequencies.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.