Recommend
7 
 Thumb up
 Hide
13 Posts

BoardGameGeek» Forums » Everything Else » Chit Chat

Subject: pi-Day puzzles (from Guardian newspaper) rss

Your Tags: Add tags
Popular Tags: [View All]
Julius Waller
Belgium
Brussels
flag msg tools
badge
Avatar
mbmbmbmbmb
1) Pictured below are three identical boxes packed with pies. You can assume that all pies are exactly the same height. Which box contains the most pie?





Spoiler (click to reveal)
A, B and C contain equal amounts of pie.

The tastiest solution is to consider box B as a square box made from four smaller square boxes, and box C as a square box made from 16 smaller square boxes. Pie fills the same percentage of each box, whatever the size of the box. So pie must fill the same percentage of A, B and C. In other words, the amount of pie is the same in each box.

But if you wanted to overcomplicate things, you can also solve with pi. As you remember from school, the area of a circle is pi x (radius)2, or πr2. Let the radius of the smallest pies (in C) be r, which means the radius of the medium pies (in B) is 2r and the radius of the big pi is 4r. Then the area of pie in A is π (4r)2 = 16r2, the area of pie in B is 4 x π (2r)2 = 16r2, and the area of pie in C is 16π (r)2 = 16r2. All the same!


2) One hundred computers are connected in a 10x10 network grid, as below. At the start exactly nine of them are infected with a virus. The virus spreads like this: if any computer is directly connected to at least 2 infected neighbours, it will also become infected.

Will the virus infect all 100 computers?



The image shows a possible example of the initial infection. You can try to fill it in to see if ultimately the network will consist of 100 orange dots. But the question is not asking what happens to this example. I want to know what will happen given any initial configuration of infected computers.

Spoiler (click to reveal)
Solution

No, the virus will not infect all 100 computers.

The solution is simple to understand, although you would have needed some impressive insight to get there on your own.

They key here is the perimeter of the infection. By perimeter, I mean the length of the boundary of the infection. For the infection to infect all computers, then the final boundary must be 40, since the perimeter of an infected 10x10 square is 10 + 10 + 10 + 10 = 40

Note that the infection can be a single area, or it can be made up of many separate areas. If it is many separate areas, we need to combine the perimeters of all the infected areas.

The perimeter of a single infected computer is 4, as below. So the perimeter of nine infected computers will be maximum 36, which is 4 x 9. (This is the case when no infected computers are adjacent, as in the image above. But the perimeter may be much lower. For example, if the infected computers are all on the same row, the boundary will only be 9 + 9 + 1 + 1 = 20)

The beautiful part of this problem is the fact that the perimeter of the infection never increases as the infection grows. Consider what happens when an uninfected computer is infected by two computers. Two of its sides are absorbed into the infected area, and the other two become part of the perimeter of the infected area. The perimeter loses 2 and gains 2, a net change of 0. We can see this in the mini-grid below. In A, the infected area has a perimeter 8. In B, a new computer is infected, yet the perimeter of the infected area remains 8. Likewise in C, another computer is infected, and the perimeter remains 8.

If an uninfected computer is infected by three computers, three sides are absorbed into the infection, and its fourth side becomes part of the perimeter, a net loss to the perimeter of 2. And if an unifected computer is infected by four computers, the net loss to the perimeter is 4.

So, if the perimeter of nine infected computers is at most 36, and it can never increase, then it can never reach 40, which means the infection cannot spread to all computers. Solved!


The second problem is beautiful - the explanation given in the original article as to why its related to pi is disappointing though!
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Jones
United States
Wilsonville
Oregon
flag msg tools
mbmbmbmbmb
TrustyJules wrote:
The solution is simple to understand, although you would have needed some impressive insight to get there on your own.


No, not really. There is a simpler solution than the one given.

Spoiler (click to reveal)
Consider a solid line of infected computers. This line cannot infect any more computers as there no adjacent nodes touching two computers. If you place a second line of the same length adjacent to the first one, you have the same situation: there are no uninfected nodes touching the first one. You can continue adding lines to this in any way you want to, but the end result is that any filled rectangle cannot continue to infect. It is impossible for the infection to spread without another computer outside this box to feed it. In the original diagram, even if we assume that the infections can take over the entire 6x7 grid in the lower right corner (the rectangle that contains all of the original infections), this is as far as the infection can go. There are no more computers allowing it spread beyond that rectangle.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Jones
United States
Wilsonville
Oregon
flag msg tools
mbmbmbmbmb
TrustyJules wrote:
The beautiful part of this problem is the fact that the perimeter of the infection never increases as the infection grows.

Consider what happens when an uninfected computer is infected by two computers. Two of its sides are absorbed into the infected area, and the other two become part of the perimeter of the infected area. The perimeter loses 2 and gains 2, a net change of 0. We can see this in the mini-grid below. In A, the infected area has a perimeter 8. In B, a new computer is infected, yet the perimeter of the infected area remains 8. Likewise in C, another computer is infected, and the perimeter remains 8.

So, if the perimeter of nine infected computers is at most 36, and it can never increase, then it can never reach 40, which means the infection cannot spread to all computers. Solved!


Actually, I don't consider this to be an accurate solution either. While it does prove that that the perimeter never gets larger, it does not prove that perimeter must get smaller. The line I have bolded above shows that you can add a node to the grid without making the perimeter smaller. This means that the proof fails to show that growth has to stop. Consider placing ten infected nodes in the grid along either diagonal. This arrangement will eventually infect the entire grid. However, you only started with 10 nodes with a perimeter of 40. By their logic, you can only have a maximum of 50 infected computers, but I just infected 100.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
7 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Exit 191
United States
Buckeye
Arizona
flag msg tools
Look to the past and learn for the future.
badge
Lets go Celts!
Avatar
mbmbmbmbmb
5 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Byron S
United States
Ventura
California
flag msg tools
I don't remember what I ate last night
badge
but I can spout off obscure rules to all sorts of game like nobody's business!
Avatar
mbmbmbmbmb
davypi wrote:
TrustyJules wrote:
The beautiful part of this problem is the fact that the perimeter of the infection never increases as the infection grows.

Consider what happens when an uninfected computer is infected by two computers. Two of its sides are absorbed into the infected area, and the other two become part of the perimeter of the infected area. The perimeter loses 2 and gains 2, a net change of 0. We can see this in the mini-grid below. In A, the infected area has a perimeter 8. In B, a new computer is infected, yet the perimeter of the infected area remains 8. Likewise in C, another computer is infected, and the perimeter remains 8.

So, if the perimeter of nine infected computers is at most 36, and it can never increase, then it can never reach 40, which means the infection cannot spread to all computers. Solved!


Actually, I don't consider this to be an accurate solution either. While it does prove that that the perimeter never gets larger, it does not prove that perimeter must get smaller. The line I have bolded above shows that you can add a node to the grid without making the perimeter smaller. This means that the proof fails to show that growth has to stop. Consider placing ten infected nodes in the grid along either diagonal. This arrangement will eventually infect the entire grid. However, you only started with 10 nodes with a perimeter of 40. By their logic, you can only have a maximum of 50 infected computers, but I just infected 100.

The question specifically asks about a grid with only 9 starting nodes, so your example with 10 doesn't apply.

Since the grid starts with 9 infections, its perimeter is at most 36. There are only 3 ways to add a node, and all of them either decrease the perimeter or fail to increase it. There's no way for the perimeter to get to the required 40 that would encompass the whole square.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Knock knock open up the door it's Riel
Netherlands
Tilburg
It's wurples all the way down.
flag msg tools
designer
badge
Clockmakers lie
Avatar
mbmbmbmbmb
davypi wrote:
TrustyJules wrote:
The solution is simple to understand, although you would have needed some impressive insight to get there on your own.


No, not really. There is a simpler solution than the one given.

Spoiler (click to reveal)
Consider a solid line of infected computers. This line cannot infect any more computers as there no adjacent nodes touching two computers. If you place a second line of the same length adjacent to the first one, you have the same situation: there are no uninfected nodes touching the first one. You can continue adding lines to this in any way you want to, but the end result is that any filled rectangle cannot continue to infect. It is impossible for the infection to spread without another computer outside this box to feed it. In the original diagram, even if we assume that the infections can take over the entire 6x7 grid in the lower right corner (the rectangle that contains all of the original infections), this is as far as the infection can go. There are no more computers allowing it spread beyond that rectangle.

Yes, but that assumes the 9 nodes are in a single rectangle smaller than 10x10. The problem makes no such assumption. You can infect a row or column that was previously without infections: will infect the middle node.

You could do a proof with rectangles, either iteratively from a smaller square and working to 10x10 with 9 nodes or do something with empty lines and corners and rectangles, but the given solution is far more elegant.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Jones
United States
Wilsonville
Oregon
flag msg tools
mbmbmbmbmb
runtsta wrote:
The question specifically asks about a grid with only 9 starting nodes, so your example with 10 doesn't apply.


Fine, but I've still done enough work to show that their proof is insufficient. Place the nine nodes adjacent to each other along a diagonal. You can still infect 81 computers this way, which is twice as large as the perimeter size of 40 they use at the end of the proof. The problem is that the work they have done regarding the size of the perimeter doesn't actually say anything about the size of the final infected area.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Jones
United States
Wilsonville
Oregon
flag msg tools
mbmbmbmbmb
purplewurple wrote:
Yes, but that assumes the 9 nodes are in a single rectangle smaller than 10x10. The problem makes no such assumption.


My bad. I misread the problem. I'm not even sure iterative rectangles would work as a proof as you would have to be able to prove that all the rectangles are at least two spaces apart.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Knock knock open up the door it's Riel
Netherlands
Tilburg
It's wurples all the way down.
flag msg tools
designer
badge
Clockmakers lie
Avatar
mbmbmbmbmb
davypi wrote:
runtsta wrote:
The question specifically asks about a grid with only 9 starting nodes, so your example with 10 doesn't apply.


Fine, but I've still done enough work to show that their proof is insufficient. Place the nine nodes adjacent to each other along a diagonal. You can still infect 81 computers this way, which is twice as large as the perimeter size of 40 they use at the end of the proof. The problem is that the work they have done regarding the size of the perimeter doesn't actually say anything about the size of the final infected area.

The idea is that 9 separate nodes have a perimeter of 9x4 = 36. A 9x9 square also has a perimeter of 36 (9 on each side). A 10x10 square would have a perimeter of 40, which is impossible to reach with 9 starting nodes.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Julius Waller
Belgium
Brussels
flag msg tools
badge
Avatar
mbmbmbmbmb
davypi wrote:
runtsta wrote:
The question specifically asks about a grid with only 9 starting nodes, so your example with 10 doesn't apply.


Fine, but I've still done enough work to show that their proof is insufficient. Place the nine nodes adjacent to each other along a diagonal. You can still infect 81 computers this way, which is twice as large as the perimeter size of 40 they use at the end of the proof. The problem is that the work they have done regarding the size of the perimeter doesn't actually say anything about the size of the final infected area.


Forgive me for possibly being obtuse but 9 nodes in a diagonal would infect nothing and therefore confirm the solution. Or did I misunderstand what you mean?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
David Jones
United States
Wilsonville
Oregon
flag msg tools
mbmbmbmbmb
TrustyJules wrote:
Forgive me for possibly being obtuse but 9 nodes in a diagonal would infect nothing and therefore confirm the solution. Or did I misunderstand what you mean?


Four nodes in a diagonal would look like:
Xooo
oXoo
ooXo
oooX

The first iteration of infection would then look like:
Xxoo
xXxo
oxXx
ooxX

The upper case X represents the initial infection. You can see that the lower case xs are all adjacent to two existing infections.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Byron S
United States
Ventura
California
flag msg tools
I don't remember what I ate last night
badge
but I can spout off obscure rules to all sorts of game like nobody's business!
Avatar
mbmbmbmbmb
davypi wrote:
runtsta wrote:
The question specifically asks about a grid with only 9 starting nodes, so your example with 10 doesn't apply.


Fine, but I've still done enough work to show that their proof is insufficient. Place the nine nodes adjacent to each other along a diagonal. You can still infect 81 computers this way, which is twice as large as the perimeter size of 40 they use at the end of the proof. The problem is that the work they have done regarding the size of the perimeter doesn't actually say anything about the size of the final infected area.

I think you've figured this out, but for the sake of clarity, you're confusing perimeter (computers adjacent to the infection) with area (the number of infected computers). As the infected area grows larger, its perimeter does not, and in many cases, its perimeter will grow smaller.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.