• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Chess numbers

 
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to solve this problem but not able to.(Taken from Mathematical Circles(Russian experience)).
On 8x8 chess board, numbers from 1 to 64 are written . Each number is written exactly once.
Prove that you can always find one pair of adjacent squares(which share common edge) such that difference in their numbers is at least 5.
 
Ranch Foreman
Posts: 3268
20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Consider two squares (not necessarily adjacent) - one at (x1, y1), and the other at (x2, y2). The first point has number N1 and the second has number N2. The shortest path between them has length abs(x2-x1) + abs(y2-y1), if we only use horizontal moves or vertical moves. If we consider how N changes as we move from square to square, we know that average rate of change on a particular path must be avg = (N2 - N1)/(abs(x2-x1) + abs(y2-y1)).

Now, somewhere on the 64 squares there's a 1 and a 64. Let those be N1 and N2. What's the smallest possible value of avg? The numerator is clearly 63. The largest possible value for the denominator is if N1 and N2 are on opposite corners, which are 7 squares apart vertically, and 7 horizontally. So the smallest possible value of avg is 63/14 = 4.57. Since all individual changes in N must be integers, we know that at least one change must be 5 or greater. And at least one must be 4 or less.
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks. Got it.
 
Ranch Hand
Posts: 1168
11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mike Simmons wrote:[minimum average difference between 1 and 64 must be > 4.]



Nice insight!

I had worked out a proof that starts with some number in the middle of the board and proves that the in placing the next so many numbers, you are forced to end up with two adjacent numbers that are more than 4 apart. I was dreading typing in all the verbiage for the proof.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!