Logo PTI Logo FedCSIS

Communication Papers of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 32

Dirichlet's principle revisited: An inverse Dirichlet's principle definition and its bound estimation improvement using stochastic combinatorics

, , ,

DOI: http://dx.doi.org/10.15439/2022F221

Citation: Communication Papers of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 32, pages 113–116 ()

Full text

Abstract. Dirichlet's principle, also known as a pigeonhole principle, claims that if n item are put into m containers, with n > m, then there is a container that contains more than one item. In this work, we focus rather on an inverse Dirichlet's principle (by switching items and containers), which is as follows: considering n items put in m containers, when n < m, then there is at least one container with no item inside. Furthermore, we refine Dirichlet's principle using discrete combinatorics within a probabilistic framework. Applying stochastic fashion on the principle, we derive the number of items n may be even greater than or equal to m, still very likely having one container without an item. The inverse definition of the problem rather than the original one may have some practical applications, particularly considering derived effective upper bound estimates for the items number, as demonstrated using some applied mini-studies.

References

  1. Lynn Loomis and Shlomo Sternberg. “Potential theory in E “. In: Advanced Calculus. World Scientific, Mar. 2014, pp. 474–508. http://dx.doi.org/10.1142/9789814583947_0013.
  2. Giridhar D. Mandyam, Nasir U. Ahmed, and Neeraj Magotra. “DCT-based scheme for lossless image compression”. In: SPIE Proceedings. SPIE, Apr. 1995. http://dx.doi.org/10.1117/12.206386.
  3. Yakir Aharonov, Fabrizio Colombo, Sandu Popescu, et al. “Quantum violation of the pigeonhole principle and the nature of quantum correlations”. In: Proceedings of the National Academy of Sciences 113.3 (Jan. 2016), pp. 532–535. http://dx.doi.org/10.1073/pnas.1522411112.
  4. Benoit Rittaud and Albrecht Heeffer. “The Pigeonhole Principle, Two Centuries Before Dirichlet”. In: The Mathematical Intelligencer 36.2 (Aug. 2013), pp. 27–29. http://dx.doi.org/10.1007/s00283-013-9389-1.
  5. Mario Cortina Borja and John Haigh. “The birthday problem”. In: Significance 4.3 (Aug. 2007), pp. 124–127. http://dx.doi.org/10.1111/j.1740-9713.2007.00246.x.