اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA New Variation of Hat Guessing Games
129
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Several variations of hat guessing games have been popularly discussed in recreational mathematics. In a typical hat guessing game, after initially coordinating a strategy, each of $n$ players is assigned a hat from a given color set. Simultaneously, each player tries to guess the color of his/her own hat by looking at colors of hats worn by other players. In this paper, we consider a new variation of this game, in which we require at least $k$ correct guesses and no wrong guess for the players to win the game, but they can choose to pass. A strategy is called {em perfect} if it can achieve the simple upper bound $frac{n}{n+k}$ of the winning probability. We present sufficient and necessary condition on the parameters $n$ and $k$ for the existence of perfect strategy in the hat guessing games. In fact for any fixed parameter $k$, the existence of perfect strategy can be determined for every sufficiently large $n$. In our construction we introduce a new notion: $(d_1,d_2)$-regular partition of the boolean hypercube, which is worth to study in its own right. For example, it is related to the $k$-dominating set of the hypercube. It also might be interesting in coding theory. The existence of $(d_1,d_2)$-regular partition is explored in the paper and the existence of perfect $k$-dominating set follows as a corollary.
قيم البحث
اقرأ أيضاً
Let $S$ be a set of positive integers, and let $D$ be a set of integers larger than $1$. The game $i$-Mark$(S,D)$ is an impartial combinatorial game introduced by Sopena (2016), which is played with a single pile of tokens. In each turn, a player can
subtract $s in S$ from the pile, or divide the size of the pile by $d in D$, if the pile size is divisible by $d$. Sopena partially analyzed the games with $S=[1, t-1]$ and $D={d}$ for $d otequiv 1 pmod t$, but left the case $d equiv 1 pmod t$ open. We solve this problem by calculating the Sprague-Grundy function of $i$-Mark$([1,t-1],{d})$ for $d equiv 1 pmod t$, for all $t,d geq 2$. We also calculate the Sprague-Grundy function of $i$-Mark$({2},{2k + 1})$ for all $k$, and show that it exhibits similar behavior. Finally, following Sopenas suggestion to look at games with $|D|>1$, we derive some partial results for the game $i$-Mark$({1}, {2, 3})$, whose Sprague-Grundy function seems to behave erratically and does not show any clean pattern. We prove that each value $0,1,2$ occurs infinitely often in its SG sequence, with a maximum gap length between consecutive appearances.
In a polyomino set (1,2)-achievement game the maker and the breaker alternately mark one and two previously unmarked cells respectively. The makers goal is to mark a set of cells congruent to one of a given set of polyominoes. The breaker tries to pr
event the maker from achieving his goal. The teams of polyominoes for which the maker has a winning strategy is determined up to size 4. In set achievement games, it is natural to study infinitely large polyominoes. This enables the construction of super winners that characterize all winning teams up to a certain size.
We give a new proof that any candy-passing game on a graph G with at least 4|E(G)|-|V(G)| candies stabilizes. (This result was first proven in arXiv:0807.4450.) Unlike the prior literature on candy-passing games, we use methods from the general theor
y of chip-firing games which allow us to obtain a polynomial bound on the number of rounds before stabilization.
Given a family of graphs $mathcal{F}$, we define the $mathcal{F}$-saturation game as follows. Two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that crea
tes a subgraph in $mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $textrm{sat}_g(n,mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally. In general there are very few non-trivial bounds on the order of magnitude of $textrm{sat}_g(n,mathcal{F})$. In this work, we find collections of infinite families of cycles $mathcal{C}$ such that $textrm{sat}_g(n,mathcal{C})$ has linear growth rate.
We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar
in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
