TL;DR If you want to design the perfect lottery where participants believe they have a chance to win but can never actually do so, you’ll need the expertise of a skilled mathematician. However, with enough data, a capable statistical programmer can unravel the mechanism and expose the illusion.
Updated 2025-01-05
Introduction
Kasa Romana is a well-known lottery in Poland, organized by the Amino food company. Originating in the 1990s, this lottery gives participants the chance to win cash prizes by collecting coupons that sum up to round hundreds, up to 1000 PLN. In this blog post, we delve into the data from the last Kasa Romana event, held in 2016, and analyze it using the Knapsack Algorithm implemented in R.
The data for this analysis was meticulously gathered by BezKanalu, a popular Polish YouTube channel known for testing promotional products. They collected an impressive 1002 coupons from the final event, providing a robust dataset to explore. The goal? To uncover patterns in the data and assess whether these coupons could realistically lead to a monetary win.
To tackle this challenge, I utilized the Knapsack Algorithm, a well-established optimization technique. The algorithm identifies the optimal way to select items (in this case, coupons) that meet specific constraints (summing to full hundreds) while maximizing value. Using R, I implemented this algorithm to determine if any subset of the collected coupons could satisfy the winning conditions of the lottery.
Surprisingly, the analysis revealed that no combination of coupons from the dataset allowed participants to win real money. This finding was further reinforced through a theoretical proof using modular arithmetic.
In conclusion, this blog post highlights the power of the Knapsack Algorithm as a tool for solving complex optimization problems like the Kasa Romana lottery. The analysis not only sheds light on the patterns and limitations of the lottery but also demonstrates how programming and mathematical approaches can provide valuable insights into real-world scenarios.
Apply Knapsack Algorithm on Lottery Coupons
First we will define the lottery coupons and analyze them.
It is worth to try to understand the data patterns before running the Knapsack Algorithm.
Sorted unique values:
Sorted table of frequencies:
Histrogram might be helpful to find certain patterns:
Numbers seems to be generated from 2 specific patterns:
- multiplication of 13 starting from 26
- multiplication of 13 plus 165
We can easily confirm that all of the coupons comes from this 2 sequences.
Single Knapsack Problem
Knapsack is an optimization method, linear programming for integers. Each of 1000 coupons is replicated 10 times before the procedure. This replication step is not needed to get this certain results although it will be even more convincing. Remainder, I was looking for set of coupons which sum to full hundreds (100, 200, …) up to 1000.
Taking into account only coupons provided there is NO chance to win anything.
This seems to no be surprising when we know from what sequences the coupons come from.
Theoretical Proof: Modular Arithmetic Analysis
While the Knapsack algorithm provides computational evidence, I also used theoretical modular arithmetic to validate this result mathematically.
Key Sequences
The coupon values are derived from two modular arithmetic sequences:
- Sequence 1: Residues of \(13k \mod 100\) for \(k \in \mathbb{Z}\):
\[ S_1 = \{13, 26, 39, 52, 65, 78, 91, 4, 17, 30, \dots\}. \]
- Sequence 2: Residues of \(165 + 13b \mod 100\), rewritten as \(65 + 13b \mod 100\) for \(b \in \mathbb{Z}\):
\[ S_2 = \{65, 78, 91, 4, 17, 30, 43, \dots\}. \]
Sum of Coupons
Any sum of coupons from \(S_1 \cup S_2\) can be expressed as:
\[ \text{Sum} = 13 \left( \sum k_i + \sum b_j \right) + \sum c_j \mod 100, \]
where:
- \(\sum k_i\) comes from \(S_1\),
- \(\sum b_j\) comes from \(S_2\),
- \(\sum c_j\) represents offsets 0 for \(S_1\), 65 for \(S_2\).
Factoring 13:
\[ \text{Sum} = 13 \left( \sum k_i + \sum b_j \right) + \sum c_j \mod 100. \]
Why No Sum Can Sum Up to Full Hundreds
The number 13 is coprime to 100, meaning their greatest common divisor is 1. As a result Multiples of 13 mod 100 complete residue cycle: \(\{13, 26, 39, 52, 65, 78, 91, 4, 17, 30, \dots\}\). This sequence never includes \(0 \mod 100\) because multiples of 13 mod 100 has no integer solutions. Thus, \(13 \left( \sum k_i + \sum b_j \right) \mod 100\) also cannot equal \(0 \mod 100\) (sum to full hundreds).
The term \(\sum c_j\) introduces a shift, but it does not affect the impossibility of summing to \(0 \mod 100\). Offsets from \(S_2\): The offsets \((c_j = 65\) for \(S_2\) shift the residue cycle of \(13 \left( \sum k_i + \sum b_j \right)\), creating \(13 \left( \sum k_i + \sum b_j \right) + 65 \mod 100.\) This shifted cycle is still disjoint from \(0 \mod 100\) because the original cycle of \(13k \mod 100\) does not include 0. For other shifts (e.g., 1, 11, or any value), the term \(\sum c_j\) merely shifts the residue cycle, but since \(13k \mod 100\) cannot align with \(0\), no shift can create \(0 \mod 100\).
Conclusion
The Knapsack Algorithm computationally confirms that no combination of Kasa Romana lottery coupons can sum up to full hundreds, making it impossible to meet the winning criteria. This conclusion is further validated by a theoretical proof using modular arithmetic, adding credibility and mathematical rigor to the findings.