• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 15:31
CET 21:31
KST 05:31
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2310[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over4Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
No more SC2 streamers on team liquid? Team Liquid Map Contest #23 Weekly Cups (Nov 9-15): Clem and herO take over Dark completes military service, returns to SC2 StarCraft open world shooter announced at BlizzCon
Tourneys
soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament RSL goes to London! 2026 Offline Finals Nov 21-22 Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
Light introduces ShieldBattery on his YouTube List of top players active on ShieldBattery BW General Discussion BGH Auto Balance -> http://bghmmr.eu/ NaDa's Body
Tourneys
KCM Race Survival 2026 Season 4 SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [Megathread] Daily Proleagues [BSL23] Ro16 Group D - Sunday 21:00 CET
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Stormgate/Frost Giant Megathread The PlayStation 5 Warcraft III: The Frozen Throne Nintendo Switch Thread Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Artificial Intelligence Thread The Big Programming Thread Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Customize Sidebar...

Website Feedback

Closed Threads



Active: 14164 users

Fun Math Problem

Blogs > EtherealDeath
Post a Reply
1 2 Next All
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
Last Edited: 2009-08-27 04:08:26
August 27 2009 02:46 GMT
#1
Yea... not sure of the solution to this.

We have a bounded interval, say [a,b]. The values of a and b are not particularly important. Let's say we are using [0,1000].

Within this bounded interval are some set number of other bounded intervals, which may or may not intersect with other bounded intervals. For example, one possible set of intervals is {[1,100],[2,36],[45,798]}.

From each bounded interval (not counting [0,1000]), you must pick exactly one point so that the least distance between two points is maximized.

What alogorithm would solve this?

EDIT: Attempt at clarification.

Basically he nth triangular number is the number of possible point pairs, each of which has a corresponding distance. For example, say we had [0,1] and [988,1000]. Then we would pick the points 0 and 1000, yielding a distance of 1000, because that choice of points means that the distance between the two closest points is maximized. We could have choise 1 and 988, but the distance would be decreased, so it's not the optimum choice.

Another way of putting it is that you want to choose the points so that the two closest ones are as far apart as possible.

*
Saracen
Profile Blog Joined December 2007
United States5139 Posts
August 27 2009 02:52 GMT
#2
That's not fun at all!
Crunchums
Profile Blog Joined December 2008
United States11144 Posts
August 27 2009 02:52 GMT
#3
I do not understand your english
brood war for life, brood war forever
prOxi.swAMi
Profile Blog Joined November 2004
Australia3091 Posts
August 27 2009 03:04 GMT
#4
You need to articulate this more clearly
Oh no
thoraxe
Profile Blog Joined March 2007
United States1449 Posts
August 27 2009 03:05 GMT
#5
Plz don't tell me this is 9th grade kiddie Math for you Chinese people?
Obama singing "Kick Ass" Song: http://www.youtube.com/watch?v=yghFBt-fXmw&feature=player_embedde
illu
Profile Blog Joined December 2008
Canada2531 Posts
Last Edited: 2009-08-27 03:32:31
August 27 2009 03:32 GMT
#6
I am not sure if it is even a math problem, since the word "algorithm" is used. Other than that, I do not understand the problem.

Might as well type it in Chinese. =P
:]
blue_arrow
Profile Blog Joined July 2008
1971 Posts
August 27 2009 03:33 GMT
#7
On August 27 2009 12:05 thoraxe wrote:
Plz don't tell me this is 9th grade kiddie Math for you Chinese people?


8th grade
| MLIA | the weather sucks dick here
Maero
Profile Joined December 2007
349 Posts
August 27 2009 03:35 GMT
#8
just take the average? (e.g. (b+a)/2)

i probably don't understand the problem though, like everyone else
MamiyaOtaru
Profile Blog Joined September 2008
United States1687 Posts
August 27 2009 03:40 GMT
#9
He must think homework is fun
Leg[end]
Profile Blog Joined May 2009
United States241 Posts
August 27 2009 04:02 GMT
#10
On August 27 2009 11:46 EtherealDeath wrote:
Yea... not sure of the solution to this.

We have a bounded interval, say [a,b]. The values of a and b are not particularly important. Let's say we are using [0,1000].

Within this bounded interval are some number of other bounded intervals, which may or may not intersect with other bounded intervals.

From each bounded interval (not counting [0,1000]), you must pick one point from each bounded interval so that the least distance between two points is maximized.

What alogorithm would solve this?


The contrast between this thread's topic and its actual contents is staggering oo;
Legends Never Die ;;
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
August 27 2009 04:06 GMT
#11
attempted to clarify.
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
August 27 2009 04:07 GMT
#12
On August 27 2009 12:35 Maero wrote:
just take the average? (e.g. (b+a)/2)

i probably don't understand the problem though, like everyone else



That I know is definitely not the solution. Among other things the taking of the average makes no sense in that you would be picking one point, but there could many many different intervals, which would mean more than one point.
brian
Profile Blog Joined August 2004
United States9644 Posts
August 27 2009 04:28 GMT
#13
shouldnt it always be b-a? assuming we have infinitely many intervals.
Severedevil
Profile Blog Joined April 2009
United States4839 Posts
August 27 2009 04:32 GMT
#14
Well, there's an obvious crappy algorithm.

It's easy to check whether you can pick points such that each pair is separated by a minimum distance of d. So you can do a binary search on d, and continue until you're as close to the exact answer as you're asked to get.

I'm looking for a better solution, but that will work.
My strategy is to fork people.
Muirhead
Profile Blog Joined October 2007
United States557 Posts
Last Edited: 2009-08-27 04:53:20
August 27 2009 04:49 GMT
#15
I do not know (or believe) that there is a terribly simple formula for the answer.

If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.

The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.

Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.

I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.
starleague.mit.edu
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
August 27 2009 05:25 GMT
#16
On August 27 2009 13:49 Muirhead wrote:
I do not know (or believe) that there is a terribly simple formula for the answer.

If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.

The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.

Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.

I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.


Hm... I'm afraid I don't quite see the applicability of recursion on this problem. It seems that considering a_1 would not only change a_2 but also a_3, a_4,... which makes you recalculate everything, as the new minimum might not be between a_1 and a_2 but rather a_k and a_(k+t) for some k.
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
Last Edited: 2009-08-27 07:18:37
August 27 2009 07:18 GMT
#17
用中文说吧,我翻译
send me a pm to remind me to translate it.
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
SiegeTanksandBlueGoo
Profile Blog Joined December 2007
China685 Posts
August 27 2009 07:26 GMT
#18
This is sort of like Euler's method in calculus, except you're trying to find a specific number instead of the slope....

Then again, the slope is a specific number so maybe you can think about using that.
What does the scouter say about his macro level? It's Over 9000 minerals!
Muirhead
Profile Blog Joined October 2007
United States557 Posts
August 27 2009 09:56 GMT
#19
My argument definitely works. I know a lot of people on this site spurt nonsense solutions to these kinds of questions, but I do actually have a math/IMO background . It's a little complicated, but if you think about it you'll understand it. I am well aware that changing a_1 can change every other a_i.

Alternatively, note that my argument proves that the coordinates of the solution points are rational linear combinations of the coordinates of the endpoints. Furthermore, the argument provides natural bounds on the denominators of the coefficients. Thus, we only need to check a finite number of d as in severedevil's argument.
starleague.mit.edu
ninjafetus
Profile Joined December 2008
United States231 Posts
August 27 2009 12:52 GMT
#20
Restating the problem more clearly for anyone still confused.

You are given an closed interval [a,b], and some number of closed subintervals S_i = [a_i, b_i].
For each S_i, choose a c_i contained in [a_i, b_i] such that min_{i,j} (c_i, c_j) is maximized.

Wait, that might not be any more clear at all, save for math people who already get it...

In other words, each subinterval gets a point. Choose the points so that the distance between the two closest points is maximized over all possible choices of points.
1 2 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 2h 29m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
mouzHeroMarine 378
elazer 314
ProTech159
JuggernautJason48
SpeCial 30
EmSc Tv 20
StarCraft: Brood War
Britney 14260
Shuttle 418
Dota 2
420jenkins352
monkeys_forever332
capcasts6
League of Legends
Trikslyr62
Heroes of the Storm
Liquid`Hasu421
Other Games
FrodaN1520
Beastyqt632
B2W.Neo229
ArmadaUGS131
C9.Mang0112
QueenE88
NightEnD2
Organizations
Other Games
BasetradeTV122
StarCraft 2
EmSc Tv 20
EmSc2Tv 20
[ Show 13 non-featured ]
StarCraft 2
• Reevou 6
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV732
League of Legends
• Stunt212
Other Games
• imaqtpie799
• Shiphtur468
Upcoming Events
Replay Cast
2h 29m
KCM Race Survival
13h 29m
Ultimate Battle
15h 29m
ZerO vs Bisu
Big Brain Bouts
20h 29m
FoxeR vs Bly
LetaleX vs MilkiCow
Reynor vs Lambo
RSL Revival
1d 14h
BSL
1d 23h
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
2 days
IPSL
2 days
Ret vs ggnore13
nOmaD vs Aether
BSL
2 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
3 days
[ Show More ]
WardiTV Weekly
3 days
Kung Fu Cup
4 days
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
5 days
The PondCast
6 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.