3x3 grid, pigeonhole principle (1 Viewer)

My namehih

New Member
Joined
Mar 9, 2020
Messages
2
Gender
Female
HSC
2020
Consider a with 3×3 grid where each cell contains a number of coins; for example, the following represents a possible configuration of coins on the grid (the integer in each cell is the number of coins in that cell):
12 3 1
1 8 4
2 13 0
This configuration is transformed in stages as follows: in each step, every cell sends a coin to all of its neighbors (horizontally or vertically, not diagonally), but if there aren’t enough coins in a cell to send one to each of its neighbors, it sends no coins at all. For example, the above would result in the following after one step:
11 2 3
4 7 2
1 12 2

a) Show that every staring configuration results in stable configuration (one that no longer changes in this process), or repeatedly cycles through 𝑘 configurations for some positive integer 𝑘 (i.e., those same 𝑘 configurations appear repeatedly in the sequence over and over as the transformation is applied).

b) In the case that the initial configuration eventually cycles through 𝑘 configurations, what are the possible values of 𝑘?

c) Either prove that for some positive integer 𝐵, every configuration will reach a stable configuration or a repetition of a 𝑘-cycle in 𝐵 or fewer steps, or prove there is no such 𝐵.
 
Last edited:

My namehih

New Member
Joined
Mar 9, 2020
Messages
2
Gender
Female
HSC
2020
If there are N coins total, can you show that there are at most, say, 3^N configurations containing those coins?
 
Last edited:

Pedro123

Active Member
Joined
Jun 17, 2019
Messages
106
Gender
Male
HSC
2021
I'll get to your first set (Going to class now), but for your second question, consider N items on a conveyer belt. You now have 8 dividers, which can be placed in any of the positions between or on either side of the items. The distance between 2 dividers is a value in a cell of the square. How many ways can you do this?
This is just a simple choose equation (I'll let you do it yourself)
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top