List of Publications

Tanya Khovanova

Some of my research is reflected on my webpage. Namely,

I am the author and a coauthor of many sequences in the OEIS. I have a separate web page with the list of my sequences.


  1. (with Wayne Zhao) Mathematics of a Sudo-Kurve math.HO arXiv: 1808.06713.

    We investigate a type of a Sudoku variant called Sudo-Kurve, which allows bent rows and columns, and develop a new, yet equivalent, variant we call a Sudo-Cube. We examine the total number of distinct solution grids for this type with or without symmetry. We study other mathematical aspects of this puzzle along with the minimum number of clues needed and the number of ways to place individual symbols.

  2. (with Ben Chen, Richard Chen, Joshua Guo, Shane Lee, Neil Malur, Nastia Polina, Poonam Sahoo, Anuj Sakarda, Nathan Sheffield, Armaan Tipirneni) On Base 3/2 and its Sequences math.NT arXiv: 1808.04304.

    We discuss properties of integers in base 3/2. We also introduce many new sequences related to base 3/2. Some sequences discuss patterns related to integers in base 3/2. Other sequence are analogues of famous base-10 sequences: we discuss powers of 3 and 2, Look-and-say, and sorted and reverse sorted Fibonaccis. The eventual behavior of sorted and reverse sorted Fibs leads to special Pinocchio and Oihcconip sequences respectively.

  3. Crypto Word Search

    A Crypto Word Search puzzle made as a gift exchange for G4G13.

  4. Murder at the Asylum math.HO arXiv: 1803.09607.

    I describe a puzzle I wrote for the 2018 MIT Mystery Hunt which introduced new types of people in logic puzzles. I discuss the puzzle itself, the solution, and the mathematics behind it.

  5. Coins and Logic math.HO arXiv: 1801.01143.

    We establish fun parallels between coin-weighing puzzles and knights-and-knaves puzzles.

  6. (with Dhroova Aiylam) Weighted Mediants and Fractals math.NT arXiv: 1711.01475.

    In this paper we study a natural generalization of the Stern-Brocot sequences which comes from the introduction of weighted mediants. We focus our attention on the case k=3, in which (2a+c)/(2b+d) and (a+2c)/(b+2d) are the two mediants inserted between a/b and c/d. We state and prove several properties about the cross-differences of Stern-Brocot sequences with k=3, and give a proof of the fractal-like rule that describes the cross-differences of the unit k=3 Stern-Brocot sequences, i.e. the one with usual starting terms 0/1, 1/1 and with reduction of fractions.

  7. On the Mathematics of Fraternal Birth Order Effect and the Genetics of Homosexuality q-bio.OT arXiv: arXiv q-bio.OT 1711.09692.

    Mathematicians have always been attracted to the field of genetics. I am especially interested in the mathematical aspects of research on homosexuality. Certain studies show that male homosexuality may have a genetic component that is correlated with female fertility. Other studies show the existence of the fraternal birth order effect, that is the correlation of homosexuality with the number of older brothers.
    This paper is devoted to the mathematical aspects of how these two phenomena are interconnected. In particular, I show that the fraternal birth order effect produces a correlation between homosexuality and maternal fecundity. Vice versa, I show that the correlation between homosexuality and female fecundity implies the increase of the probability of the younger brothers being homosexual.

  8. PRIMES STEP Plays Games (Pratik Alladi, Neel Bhalla, Nathan Sheffield, Eddie Song, William Sun, Andrew The, Alan Wang, Naor Wiesel, Kevin Zhang, Kevin Zhao) math.CO arXiv: 1707.07201. Published in Minnesota Journal of Undergraduate Mathematics, Vol 4, No 1, pp. 1-12, 2018.

    A group of students in 7-9 grades are inventing combinatorial impartial games. The games are played on graphs, piles, and grids. We found winning positions, optimal strategies, and other interesting facts about the games.

  9. On Variations of Nim and Chomp (June Ahn, Benjamin Chen, Richard Chen, Ezra Erives, Jeremy Fleming, Michael Gerovitch, Tejas Gopalakrishna, Neil Malur, Nastia Polina, Poonam Sahoo) math.CO arXiv: 1705.06774.

    We study two variations of Nim and Chomp which we call Monotonic Nim and Diet Chomp. In Monotonic Nim the moves are the same as in Nim, but the positions are non-decreasing numbers as in Chomp. Diet-Chomp is a variation of Chomp, where the total number of squares removed is limited.

  10. (with Konstantin Knop) Coins that Change Their Weights math.CO arXiv: 1611.09201.

    As in many coin puzzles, we have several identical-looking coins, with one of them fake and the rest real. The real coins weigh the same. Our fake coin is special in that it can change its weight. The coin can pretend to be a real coin, a fake coin that is lighter than a real one, and a fake coin that is heavier than a real one. In addition to this, each time the coin is on the scale, it changes its weight in a predetermined fashion.
    In this paper, we seek to find our fake coin using a balance scale and the smallest number of weighings.
    We consider different possibilities for the fake coin. We discuss coins that change weight between two states or between three states. The 2- state coin that changes weight from lighter to real and back has been studied before, so we concentrate on the 2-state coin that changes weight from lighter to heavier, and back. We also study the 3-state coin, which changes its weight from lighter to heavier to real, and back to lighter.
    Given the total number of coins and the starting state of the fake coin, we calculate the smallest number of weighings needed to identify the fake coin. We provide an oblivious optimal strategy for this number of weighings. We also discuss what happens if the starting state is not known or mixed. In such cases, adaptive strategies are often more powerful than oblivious ones.

  11. (with Rafael M. Saavedra) Discreet Coin Weighings and the Sorting Strategy math.CO arXiv: 1609.07466.

    In 2007, Alexander Shapovalov posed an old twist on the classical coin weighing problem by asking for strategies that manage to conceal the identities of specific coins while providing general information on the number of fake coins. In 2015, Diaco and Khovanova studied various cases of these "discreet strategies" and introduced the revealing factor, a measure of the information that is revealed.

    In this paper we discuss a natural coin weighing strategy which we call the sorting strategy: divide the coins into equal piles and sort them by weight. We study the instances when the strategy is discreet, and given an outcome of the sorting strategy, the possible number of fake coins. We prove that in many cases, the number of fake coins can be any value in an arithmetic progression whose length depends linearly on the number of coins in each pile. We also show the strategy can be discreet when the number of fake coins is any value within an arithmetic subsequence whose length also depends linearly on the number of coins in each pile. We arrive at these results by connecting our work to the classic Frobenius coin problem. In addition, we calculate the revealing factor for the sorting strategy.

  12. (with Shuheng Niu) m-Modular Wythoff math.CO arXiv: 1608.01025.

    We discuss a variant of Wythoff's Game, m-Modular Wythoff's Game, and identify the winning and losing positions for this game.

  13. with Benjamin Chen, Ezra Erives, Leon Fan, Michael Gerovitch, Jonathan Hsu, Neil Malur, Ashwin Padaki, Nastia Polina, Will Sun, Jacob Tan, Andrew The) Alternator Coins math.CO arXiv: arXiv math.CO 1605.05601, published in Math Horizons, v.25.1, pp. 22-25, (2017).

    We introduce a new type of coin: the alternator. The alternator can pretend to be either a real or a fake coin (which is lighter than a real one). Each time it is put on a balance scale it switches between pretending to be either a real coin or a fake one. In this paper, we solve the following problem: You are given N coins that look identical, but one of them is the alternator. All real coins weigh the same. You have a balance scale which you can use to find the alternator. What is the smallest number of weighings that guarantees that you will find the alternator?

  14. Thinking Inside and Outside the Box math.GM arXiv: 1605.02232. The paper is published in G4G12 Exchange book, v1 p.238-245.

    I discuss puzzles that require thinking outside the box. I also discuss the box inside of which many people think.

  15. (with Benjamin Chen, Ezra Erives, Leon Fan, Michael Gerovitch, Jonathan Hsu, Neil Malur, Ashwin Padaki, Nastia Polina, Will Sun, Jacob Tan, Andrew The) Who Is Guilty? math.HO arXiv: arXiv math.HO 1603.08549.

    We discuss a generalization of logic puzzles in which truth-tellers and liars are allowed to deviate from their pattern in case of one particular question: "Are you guilty?"

  16. The dying art of mental math tricks. Hacker Bits, Feb, 2016. pp.24-25.

  17. (with Konstantin Knop and Oleg Polubasov) Chameleon Coins math.HO arXiv: 1512.07338.

    We discuss coin-weighing problems with a new type of coin: a chameleon. A chameleon coin can mimic a fake or a real coin, and it can choose which coin to mimic for each weighing independently.
    We consider a mix of N coins that include exactly two non-real coins: one fake and one chameleon. The task is to use a balance to find two coins one of which has to be fake. We find bounds for the number of coins for which we can find a solution in a given number of weighings. We also introduce an important idea of solution scaling.

  18. (with Caleb Ji, Robin Park, Angela Song) Chocolate Numbers. math.CO arXiv: arXiv 1509.06093. Published in the Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.7.

    In this paper, we consider a game played on a rectangular m by n gridded chocolate bar. Each move, a player breaks the bar along a grid line. Each move after that consists of taking any piece of chocolate and breaking it again along existing grid lines, until just mn individual squares remain.
    This paper enumerates the number of ways to break an m by n bar, which we call chocolate numbers, and introduces four new sequences related to these numbers. Using various techniques, we prove interesting divisibility results regarding these sequences.

  19. (with Niket Gowravaram) On the Structure of nil-Temperley-Lieb Algebras of type A. math.CO arXiv: arXiv 1509.00462.

    We investigate nil-Temperley-Lieb algebras of type A. We give a general description of the structure of monomials formed by the generators. We also show that the dimensions of these algebras are the famous Catalan numbers by providing a bijection between the monomials and Dyck paths. We show that the distribution of these monomials by degree is the same as the distribution of Dyck paths by the sum of the heights of the peaks minus the number of peaks.

  20. (with Karan Sarkar) P-positions in Modular Extensions to Nim. math.CO arXiv: arXiv 1508.07054. Published in International Journal of Game Theory Volume 46, Issue 2, pp 547-561, 2016. DOI 10.1007/s00182-016-0545-7.

    In this paper, we consider a modular extension to the game of Nim, which we call m-Modular Nim, and explore its optimal strategy. In m-Modular Nim, a player can either make a standard Nim move or remove a multiple of m tokens in total. We develop a winning strategy for all m with 2 heaps and for odd m with any number of heaps.

  21. (with Nicholas Diaco) Weighing Coins and Keeping Secrets. math.HO cs.CR arXiv: arXiv 1508.05052. A shorter versions Privacy and Counterfeit Coins Published in the Mathematical Intelligencer, 38(3) 6–11, 2016. DOI 10.1007/s00283-016-9652-3.

    In this expository paper we discuss a relatively new counterfeit coin problem with an unusual goal: maintaining the privacy of, rather than revealing, counterfeit coins in a set of both fake and real coins. We introduce two classes of solutions to this problem — one that respects the privacy of all the coins and one that respects the privacy of only the fake coins — and give several results regarding each. We describe and generalize 6 unique strategies that fall into these two categories. Furthermore, we explain conditions for the existence of a solution, as well as showing proof of a solution's optimality in select cases. In order to quantify exactly how much information is revealed by a given solution, we also define the revealing factor and revealing coefficient; these two values additionally act as a means of comparing the relative effectiveness of different solutions. Most importantly, by introducing an array of new concepts, we lay the foundation for future analysis of this very interesting problem, as well as many other problems related to privacy and the transfer of information.

  22. Octopus Logic. Published in the book: Playing with Math: Stories from Math Circles, Homeschoolers, and Passionate Teachers (2015), pages 247-248.

  23. (with Pavel Etingof and Slava Gerovitch) Mathematical Research in High School: the PRIMES Experience, Notices, v62, pp. 910-918, (2015). The article is available at the Notices website.

    Mentioned as notable writing in The best writing on mathematics 2016.
  24. Dragons and Kasha. An extended version is at the math.HO: arXiv 1602.08488.

    Kasha-eating dragons introduce advanced mathematics. The goal of this paper is twofold: to entertain people who know advanced mathematics and inspire people who don't.

  25. (with Dhroova Aiylam) Stern-Brocot Trees from Weighted Mediants. math.NT: arXiv 1502.00682.

    In this paper we discuss a natural generalization of the Stern Brocot tree which comes from the introduction of weighted mediants. We focus our attention on the case k=3, in which (2a+c)/(2b+d) and (a+2c)/(b+2d) are the two mediants inserted between a/b and c/d. Our main result is a determination of which rational numbers between the starting terms appear in the tree. We extend this result to arbitrary reduction schemes as well.

  26. (with Alexey Radul) (Not so) Much Ado About Nothing.

    Nothing is discussed in this paper.

  27. There are no Coincidences. math.CO arXiv: arXiv 1410.2193.

    This paper is inspired by a seqfan post by Jeremy Gardiner. The post listed nine sequences with similar parities. In this paper I prove that the similarities are not a coincidence but a mathematical fact.

  28. (with Konstantin Knop) Coins of Three Different Weights. math.HO arXiv: arXiv 1409.0250.

    We discuss several coin-weighing problems in which coins are known to be of three different weights and only a balance scale can be used. We start with the task of sorting coins when the pans of the scale can fit only one coin. We prove that the optimal number of weighings for n coins is ⌈3n/2⌈ − 2. When the pans have an unlimited capacity, we can sort the coins in n + 1 weighings. We also discuss variations of this problem, when there is exactly one coin of the middle weight.

  29. (with Eric Nie and Alok Puranik) The Sierpinski Triangle and The Ulam-Warburton Automaton. math.HO arXiv: arXiv 1408.5937. Published in Math Horizons, Sep 2015, pp. 5-9 as The Pioneering Role of the Sierpinski Gasket. Also republished in the book The best writing on mathematics 2016.

    This paper is about the beauty of fractals and the surprising connections between them. We will explain the pioneering role that the Sierpinski triangle plays in the Ulam-Warburton automata and show you a number of pictures along the way.

  30. (with Joshua Xiong) Cookie Monster Plays Games. math.HO arXiv: arXiv 1407.1533, published in College Mathametics Journal, v.46(4) pp.283-293 (2015).

    We research a combinatorial game based on the Cookie Monster problem called the Cookie Monster game that generalizes the games of Nim and Wythoff. We also propose several combinatorial games that are in between the Cookie Monster game and Nim. We discuss properties of P-positions of all of these games.
    Each section consists of two parts. The first part is a story presented from the Cookie Monster's point of view, the second part is a more abstract discussion of the same ideas by the authors.

  31. Attacking ApSimon's Mints. math.HO arXiv: arXiv 1406.3012.

    ApSimon's Mints problem is a very difficult and often misunderstood counterfeit-coin puzzle. I explain the problem and suggest ways to approach it, while giving several fun exercises for the reader.

  32. (with Joshua Xiong) Nim Fractals. Combinatorics arXiv: arXiv 1405.5942. Published in the Journal of Integer Sequences, Vol. 17 (2014), Article 14.7.8.

    We enumerate P-positions in the game of Nim in two different ways. In one series of sequences we enumerate them by the maximum number of counters in a pile. In another series of sequences we enumerate them by the total number of counters.
    We show that the game of Nim can be viewed as a cellular automaton, where the total number of counters divided by 2 can be considered as a generation in which P-positions are born. We prove that the three-pile Nim sequence enumerated by the total number of counters is a famous toothpick sequence based on the Ulam-Warburton cellular automaton. We introduce 10 new sequences.

  33. Love and Math: The Heart of Hidden Reality by Edward Frenkel. A book review. Published in The College Mathematics Journal, Vol. 45, No. 3 (March 2014), pp. 217-219.

  34. Hat Puzzles. History and Overview arXiv: arXiv 1404.4973, published in Recreational Mathematics Magazine, Issue 2 (2014)

    This paper serves as the announcement of my program---a joke version of the Langlands Program. In connection with this program, I discuss an old hat puzzle, introduce a new hat puzzle, and offer a puzzle for the reader.

  35. (with Brandon Avila) Free Fibonacci Sequences. Number Theory arXiv: arXiv 1403.4614. Published in the Journal of Integer Sequences, Vol. 17 (2014), Article 14.8.5.

    This paper describes a class of sequences that are in many ways similar to Fibonacci sequences: given n, sum the previous two terms and divide them by the largest possible power of n. The behavior of such sequences depends on n. We analyze these sequences for small n: 2, 3, 4, and 5. Surprisingly these behaviors are very different. We also talk about any n. Many statements about these sequences are difficult or impossible to prove, but they can be supported by probabilistic arguments, we have plenty of those in this paper.
    We also introduce ten new sequences. Most of the new sequences are also related to Fibonacci numbers proper, not just free Fibonacci numbers.

  36. Parallel Weighings. History and Overview arXiv: arXiv 1310.7268, published as Parallel Weighings of Coins in The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2015, pp. 95-104.

    I introduce, solve and generalize a new coin puzzle that involves parallel weighings.

  37. (with Dai Yang) Fission of Halving Edges Graphs. Combinatorics arXiv: arXiv 1310.3510.

    In this paper we discuss an operation on halving edges graph that we call fission. Fission replaces each point in a given configuration with a small cluster of k points. The operation interacts nicely with halving edges, so we examine its properties in detail.

  38. (with Leigh Marie Braswell) On the Cookie Monster Problem. History and Overview arXiv: arXiv 1309.5985, published as The Cookie Monster Problem in The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2015, pp. 231-244.

    The Cookie Monster Problem supposes that the Cookie Monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number of a set is the minimum number of moves the Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. We also construct sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number between 0 and 1 inclusive.

  39. Linguistic Problems. in Puzzles in Logic, Languages and Computation, (2013), Red book pages 73-74, Green book pages 83-83.

    Four linguistic puzzle from my blog are published in the books: A Killer Puzzle (Red book, page 73), It's All Greek to Me (Red book, page 74), Made in Psilvania (Green book, page 83), Voulez-Vous Compter Ave Moi (Green book, page 84).

  40. (with Jesse Geneson and Jonathan Tidor) Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs. Combinatorics arXiv: arXiv 1307.1169. Published in Discrete Mathematics, Volume 331, Pages 83-88 (2014).

    We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

  41. A Line of Sages. Published in The Mathematical Intelligencer, September 2014, Volume 36, Issue 3, pp 44-46; DOI:10.1007/s00283-013-9415-3.

    The article is mentioned in the list of notable writing in The best writing on mathematics 2015.

    A new variation of an old hat puzzle, where sages are standing in line one behind the other.

  42. (with Leigh Marie Braswell) Cookie Monster Devours Naccis. History and Overview arXiv: arXiv 1305.4305. Published in The College Mathematics Journal, Vol. 45, No. 2 (March 2014), pp. 129-135. DOI: 10.4169/college.math.j.45.2.129.

    In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.

  43. (with Matthew Babbitt and Jesse Geneson) On k-visibility graphs. Combinatorics arXiv 1305.0505. Published in the Journal of Graph Algorithms and Applications, Vol. 19, no. 1, pp. 345-360, (2015), DOI: 10.7155/jgaa.00362.

    We examine several types of visibility graphs in which sightlines can pass through k objects. For k ≥ 1 we improve the upper bound on the maximum thickness of bar k-visibility graphs from 2k(9k−1) to 6k, and prove that the maximum thickness must be at least k+1. We also show that the maximum thickness of semi-bar k-visibility graphs is between the ceiling of 2(k+1)/3 and 2k. Moreover we bound the maximum thickness of rectangle k-visibility graphs. We also bound the maximum number of edges and the chromatic number of arc and circle k-visibility graphs. Furthermore we give a method for finding the number of edges in semi-bar k-visibility graphs based on skyscraper puzzles.

  44. (with Joel Brewster Lewis) Skyscraper Numbers. Combinatorics arXiv 1304.6445. Published in the Journal of Integer Sequences, v.16 (2013), Article 13.7.2.

    We introduce numbers depending on three parameters which we call skyscraper numbers. We discuss properties of these numbers and their relationship with Stirling numbers of the first kind, and we also introduce a skyscraper sequence.

  45. (with Dai Yang) Connected Components of Underlying Graphs of Halving Lines. Combinatorics arXiv 1304.5658. Published in Geombinatorics, XXIII(4) (2013) pp. 177-185.

    In this paper we discuss the connected components of underlying graphs of halving lines' configurations. We show how to create a configuration whose underlying graph is the union of two given underlying graphs. We also prove that every connected component of the underlying graph is itself an underlying graph.

  46. (with Ziv Scully) Efficient Calculation of Determinants of Symbolic Matrices with Many Variables. CS Symbolic Computation arXiv 1304.4691.

    Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.

  47. My IQ. A copy of my blog essay My IQ: Published in Hacker Monthly Vol. 34, (2013), p. 34.

  48. Conway's Wizards. History and Overview arXiv 1210.5460. Published in The Mathematical Intelligencer, Volume 35, Issue 4, pp 18-20 (2013). DOI:10.1007/s00283-012-9354-4. Also in the book The Best Writing on Mathematics 2014.

    I present and discuss a puzzle about wizards invented by John H. Conway.

  49. (with Dai Yang) Halving Lines and Their Underlying Graphs. Combinatorics arXiv 1210.4959. Published as On halving-edges graphs in Involve v. 11 (2018) 1, 1-11. DOI: 10.2140/involve.2018.11.1

    In this paper we study underlying graphs corresponding to a set of halving lines. We establish many properties of such graphs. In addition, we tighten the upper bound for the number of halving lines.

  50. (with Richard K. Guy, Julian Salazar) Conway's subprime Fibonacci sequences. Number Theory arXiv 1207.5099. Published in Mathematics Magazine, Vol. 87, No. 5, pp 323–337. (2014)

    It's the age-old recurrence with a twist: sum the last two terms and if the result is composite, divide by its smallest prime divisor to get the next term (e.g., 0, 1, 1, 2, 3, 5, 4, 3, 7, ...). These sequences exhibit pseudo-random behaviour and generally terminate in a handful of cycles, properties reminiscent of 3x+1 and related sequences. We examine the elementary properties of these 'subprime' Fibonacci sequences.

  51. Tricky Arithmetic. History and Overview arXiv 1204.3112. Published in the proceedings of G4GX.

    This article is an expanded version of my talk at the Gathering for Gardner, 2012.

  52. (with Andrew Buchanan, Alex Ryba) Saturated Domino Coverings. Combinatorics arXiv 1112.2115. Published at Geombinatorics XXIV(2) pp.53-68 (2014).

    A domino covering of a board is saturated if no domino is redundant. We introduce the concept of a fragment tiling and show that a minimal fragment tiling always corresponds to a maximal saturated domino covering. The size of a minimal fragment tiling is the domination number of the board. We define a class of regular boards and show that for these boards the domination number gives the size of a minimal X-pentomino covering. Natural sequences that count maximal saturated domino coverings of square and rectangular boards are obtained. These include the new sequences A193764, A193765, A193766, A193767, and A193768 of OEIS.

  53. (with Alexey Radul) Jewish Problems. History and Overview arXiv 1110.1556. Published as "Killer Problems" in The American Matheamtical Monthly Vol. 119, No. 10 (2012), pp815-823.

    This is a special collection of problems that were given to select applicants during oral entrance exams to the math department of Moscow State University. These problems were designed to prevent Jews and other undesirables from getting a passing grade. Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals. This collection therefore has mathematical as well as historical value.

  54. (with Christina Chen, Daniel A. Klain) Volume bounds for shadow covering. Metric Geometry arXiv 1109.1619. Published in Trans. Amer. Math. Soc. 366 (2014), 1161-1177. DOI: http://dx.doi.org/10.1090/S0002-9947-2013-05855-2

    For n ≥ 2 a construction is given for a large family of compact convex sets K and L in n-dimensional Euclidean space such that the orthogonal projection Lu onto the subspace u contains a translate of the corresponding projection Ku for every direction u, while the volumes of K and L satisfy Vn(K) > Vn(L).

    It is subsequently shown that, if the orthogonal projection Lu onto the subspace u contains a translate of Ku for every direction u, then the set (n/(n-1))L contains a translate of K. If follows that Vn(K) ≤ (n/(n-1))n Vn(L). In particular, we derive a universal constant bound Vn(K) ≤ 2.942 Vn(L), independent of the dimension n of the ambient space.

    Related results are obtained for projections onto subspaces of some fixed intermediate co-dimension. Open questions and conjectures are also posed.

  55. (with Sergei Konyagin) Sequences of Integers with Missing Quotients and Dense Points Without Neighbors. Combinatorics arXiv 1104.0441. Published in Discrete Mathematics 312 (2012), pp 1776-1787.

    Let A be a pre-defined set of rational numbers. We say a set of natural numbers S is an A-quotient-free set if no ratio of two elements in S belongs to A. We find the maximal asymptotic density and the maximal upper asymptotic density of A-quotient-free sets when A belongs to a particular class. It is known that in the case A = {p, q}, where p, q are coprime integers greater than one, the latest problem is reduced to evaluation of the largest number of lattice non-adjacent points in a triangle whose legs lie on coordinate axis. We prove that this number is achieved by choosing points of the same color in the checkerboard coloring.

  56. Martin Gardner's Mistake. Probability arXiv 1102.0173. Published in The College Mathematics Journal Vol 43, No. 1 (2012), pp. 20-24. Also in the book Martin Gardner in the Twenty-First Century.

    When Martin Gardner first presented the Two-Children problem, he made a mistake in its solution. Later he corrected the mistake in another publication, but unfortunately his incorrect solution is more widely known than his correction. In fact, a Tuesday-Child variation of this problem went viral in 2010, and the same flaw keeps reappearing in solutions for that problem as well. In this article, I would like to popularize Martin Gardner's correction and conduct a detailed discussion of the new problem.

  57. (with Joel Brewster Lewis) Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle. Combinatorics arXiv 1006.4135. Published in the Electronic Journal of Combinatorics, v.18 P37, (2011).

    We investigate a coin-weighing puzzle that appeared in the Moscow Math Olympiad in 1991. We generalize the puzzle by varying the number of participating coins, and deduce an upper bound on the number of weighings needed to solve the puzzle that is noticeably better than the trivial upper bound. In particular, we show that logarithmically-many weighings on a balance suffice.

  58. Odd One Out. History and Overview arXiv 1005.2700. Published in the proceedings of G4G9.

    This article covers my second talk at the Gathering for Gardner in March, 2010. It is about an Odd One Out puzzle I invented, after having been inspired by Martin Gardner. I do not like Odd One Out questions; that is why I invented one.

  59. (with Konstantin Knop and Alexey Radul) Baron Munchhausen's Sequence. Combinatorics arXiv 1003.3406. Published in the Journal of Integer Sequences, v.13 (2010), Article 10.8.7.

    We investigate a coin-weighing puzzle that appeared in the all-Russian math Olympiad in 2000. We liked the puzzle because the methods of analysis differ from classical coin-weighing puzzles. We generalize the puzzle by varying the number of participating coins, and deduce a complete solution, perhaps surprisingly, the objective can be achieved in no more than two weighings regardless of the number of coins involved.

  60. Clifford Algebras and Graphs. Combinatorics arXiv 0810.3322. Published in Geombinatorics v.XX, pp. 56-76, (2010)

    I show how to associate a Clifford algebra to a graph. I describe the structure of these Clifford graph algebras and provide many examples and pictures. I describe which graphs correspond to isomorphic Clifford algebras and also discuss other related sets of graphs. This construction can be used to build models of representations of simply-laced compact Lie groups.

  61. Jamming as Information: a Geometric Approach. History and Overview arXiv 0809.0011. Published in the Journal of Recreational Mathematics, v.35, n.2, 99-111 (2006)

    In this paper I discuss the kinds of information that can be extracted by our enemy if our jamming is too precise. I show geometric solutions for reconstructing linear routes given certain information about them, such as the shortest distance to a point or the times of entering and exiting a circle.

  62. Number Gossip. Combinatorics arXiv 0804.2277. Published in Proceedings of G4G8., v.1, 215-220.

    This article covers my talk at the Gathering for Gardner 2008, with some additions. It is related to my pet project Number Gossip.

  63. Autobiographical Numbers. Combinatorics arXiv 0803.0270. Published as "A Story of Storytelling Numbers" in Math Horizons, v.17, n.1, 14-17 (2009).

    I introduce autobiographical numbers as defined in A046043 (see Online Encyclopedia of Integer Sequences). I continue by defining and analyzing biographies, curricula vitae and complete life stories of numbers. I end with the definition of mutually-praising number pairs.

  64. 9 Divides no Odd Fibonacci. Combinatorics arXiv 0712.3509.

    I discuss numbers that divide no odd Fibonacci. The number 9 plays a special role among such numbers.

  65. How to Create a New Integer Sequence. Combinatorics arXiv 0712.2244.

    There are several standard procedures used to create new sequences from a given sequence or from a given pair of sequences. In this paper I discuss the most popular of these procedures. For each procedure, I give a definition and provide examples based on three famous sequences: the natural numbers, the prime numbers and the Fibonacci numbers. I also add my thoughts on what makes a sequence interesting. My goal is to help my readers invent new sequences, differentiate interesting sequences from boring ones, and better understand sequences they encounter.

  66. Unique Tournaments and Radar Tracking. Combinatorics arXiv 0712.1621. Published in Geombinatorics Quarterly Vol XXIII, (1) 16-26 (2013)

    The sequence counting the number of unique tournaments with n people is the same as the sequence counting non-tracking binary strings corresponding to n-2 radar observations with the tracking rule "3 out of 5 with loss 2." This fact allows us to build a bijection between unique tournaments and non-tracking binary strings.

  67. (with M. Curry and M. Flint) Decentralized Control Using Global Optimization (DCGO). AIAA Infotech@Aerospace 2007 Conference Proceedings (2007).

    Global-scope plans for the team are generated and distributed using the principle of emergent leadership to provide efficient plan generation and execution with minimal performance degradation compared to a centralized controller under delayed communications.

  68. (with Ingrid Daubechies and Konstantinos Drakakis) A Detailed Study of the Attachment Strategies of New Autonomous Systems in the AS Connectivity Graph. Internet Mathematics, v.2, n2, 185-246 (2005).

    In the first part of this paper, we use real BGP data to study some properties of the AS connectivity graph and its evolution in time. In the second part, we build a simple model that is inspired by observations made in the first part, and we discuss simulations of this model.

  69. (with J. Bernstein) Quantum groups and representations with highest weight. Quantum Algebra and Topology arXiv q-alg/9704007.

    We connect quantum groups to minimal objects in the category of representations with highest weight λ: they correspond to irreducible representations.

  70. On quantum group GLp,q(2). Quantum Algebra and Topology arXiv q-alg/9701033.

    In the Hopf algebra GLp,q(2) the determinant is central iff p=q. In this case we put determinant to be equal to 1 to get SLq(2). In this paper I consider the case when p/q is a root of unity; and, consequently, a power of the determinant is central.

  71. (with J.Bernstein) On Quantum Group SLq(2). Comm. Math. Phys., v.117, n3, 691-708 (1996).

    We show how to construct the quantum group SLq(2), starting from the Hopf algebra of regular functions on the torus, adding some natural conditions. Our approach allows us to construct metaplectic quantum groups of the SL(2)-type.

  72. Tetramodules over Hopf Algebra of Regular Functions on a Torus. IMRN, No.7, 275-284 (1994).

    Discussion of the definition of "tetramodule," (a special kind of bimodule and bicomodule), its properties, and its applications.

  73. Sturm-Liouville Operators Connected with Superanalogs of Virasoro algebra. Reports of Department of Mathematics, University of Stockholm, Sweden, 1988, No.5, 67-76.

    We describe different ways of superizing the Sturm-Liouville operator.

  74. (with O. Ovsienko) Superversion of Miura Transformations. Reports of Department of Mathematics, University of Stockholm, Sweden, 1988, No.5, 60-66.

    The Miura transformation of the Korteveg-de Vries equation can be described in terms of the Virasoro algebra. We construct the analog of the Miura transformation for the Lie superalgebras of the Neveu-Schwarz type.

  75. The Korteweg-de Vries Superequation Related to the Lie Superalgebra of Neveu-Schwarz-2 String Theory. Teor. Mat. Fiz., 72, No.2, 899-904 (1987).

    The short version of the next paper.

  76. Superization of the Korteveg-de Vries Equation Related with the Neveu-Schwarz Superalgebra NS(2). Reports of Department of Mathematics, University of Stockholm, Sweden, 1986, No.21, 58-73.

    We construct the integrable Korteveg-de Vries type super-equation related to the Neveu-Schwarz superalgebra NS(2) by means of the hamiltonian reduction method from the Kac-Moody algebra $\widehat {sl(2,1)}$.

  77. Lie Superalgebra Structure on Eigenfunctions and Jets of Resolvent's Kernel, near the Diagonal of an n-th Order Ordinary Differential Operator. in 'Integrable and Superintegrable Systems' ed. B.A.Kupershmidt. World Scientific 1990, p.321-335.

    An n-th order ordinary differential operator can be regarded as a point in the dual space of the Lie superalgebra $\widehat {gl(n,1)}$. The stabilizer of this point in the coadjoint action inherits the structure of the Lie superalgebra and can be described as the direct sum of the jets of the kernel of the resolvent of, and the eigenfunctions of, the given differential operator.

  78. Structure of Lie Superalgebras on Eigenfunctions and Jets of the Kernel of the Resolvent near the Diagonal for an n-th-order Differential Operator. Funkts. Anal. Prilozhen., 20, No.2, 162-164 (1986).

    The short version of the previous one.

  79. Lie Superalgebra osp(1,2), Neveu-Schwarz Superalgebra and Superization of Korteweg-de Vries equation. Group Theoretical Methods in Physics. Proceedings of the third seminar: Yurmala 1985. Utreht, Netherlands, VNU Science Press, 1986, v.1, 307-315.

    The description of the super Korteveg-de Vries equation and the Neveu-Schwarz superalgebra as the Hamiltonian reduction of the Lie superalgebra $\widetilde{osp(1,2)}$.

  80. The Gel'fand-Dikii Algebras and the Virasoro Algebra. Funkts. Anal. Prilozhen. 20, No.4, 332-334 (1986).

    An investigation of the Gelfand-Dikii algebras as the generalizations the of Virasoro algebra.

  81. Representation Models and Generalized Clifford Algebras. Funkts. Anal. Prilozhen., 16, No.4, 322-323 (1982).

    For every simply-laced Dynkin diagram Δ of a Lie algebra G, we construct a generalization of the Clifford algebra, CΔ. The involutive subalgebra of G can be imbedded into CΔ. Using the induced representation of the involutive subalgebra in CΔ we construct the model representation of G - the direct sum of irreducible representations taken once each.


Revised August 2008