• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 03:04
CEST 09:04
KST 16:04
  • 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
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Flash Announces Hiatus From ASL61Weekly Cups (June 23-29): Reynor in world title form?13FEL Cracov 2025 (July 27) - $8000 live event21Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
Statistics for vetoed/disliked maps Program: SC2 / XSplit / OBS Scene Switcher The SCII GOAT: A statistical Evaluation Weekly Cups (June 23-29): Reynor in world title form? PiG Sty Festival #5: Playoffs Preview + Groups Recap
Tourneys
FEL Cracov 2025 (July 27) - $8000 live event RSL: Revival, a new crowdfunded tournament series Korean Starcraft League Week 77 Master Swan Open (Global Bronze-Master 2) [GSL 2025] Code S: Season 2 - Semi Finals & Finals
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma Mutation # 477 Slow and Steady
Brood War
General
Flash Announces Hiatus From ASL Player “Jedi” cheat on CSL ASL20 Preliminary Maps SC uni coach streams logging into betting site BGH Mineral Boosts Tutorial Video
Tourneys
[BSL20] Grand Finals - Sunday 20:00 CET [Megathread] Daily Proleagues Small VOD Thread 2.0 [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Path of Exile Stormgate/Frost Giant Megathread Nintendo Switch Thread What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Trading/Investing Thread Things Aren’t Peaceful in Palestine The Games Industry And ATVI
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 529 users

Fun Math Problem - Page 2

Blogs > EtherealDeath
Post a Reply
Prev 1 2 All
ero
Profile Joined April 2009
United States66 Posts
August 27 2009 13:15 GMT
#21
On August 27 2009 11:46 EtherealDeath wrote:
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]}.


If I understand this problem correctly, then in this example the choice of points would be {100, 2, 798}, where the third number (798) could really be anything from 192 to 798.

Is this right?
starfries
Profile Blog Joined July 2009
Canada3508 Posts
August 27 2009 13:33 GMT
#22
On August 27 2009 21:52 ninjafetus wrote:
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.


That was sooooo much clearer, thanks
DJ – do you like ramen, Savior? Savior – not really. Bisu – I eat it often. Flash – I’m a maniac! | Foxer Fighting!
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
August 27 2009 21:38 GMT
#23
On August 27 2009 18:56 Muirhead wrote:
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.



Hm.. I am sort of seeing how it would be piecewise, but not totally confident on it yet. Will have to think about it some more when I can I suppose.
moriya
Profile Joined March 2009
United States54 Posts
Last Edited: 2009-08-28 05:34:55
August 28 2009 05:28 GMT
#24
Well, I am not sure if I totally get it but basically that's a smart idea.

One problem could be from the sorting. Have you assumed that the smallest point in the optimum solution must be picked from [a1,b1] so that you can run P for [a2,b2] to [an,bn]? Think about this testing data:[1,10] [1,15] [3,20] [4,5]. The smallest point in the solution is 4 which is picked from [4,5] set. So actually we need do P for n-1 times.

Correct me muirhead if I didnot get you
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.

Prev 1 2 All
Please log in or register to reply.
Live Events Refresh
Next event in 2h 56m
[ Submit Event ]
Live Streams
Refresh
StarCraft: Brood War
Leta 580
Larva 362
Barracks 53
Dota 2
XaKoH 631
League of Legends
JimRising 730
Counter-Strike
Stewie2K1060
Heroes of the Storm
Khaldor210
Other Games
WinterStarcraft658
SortOf95
kaitlyn65
ProTech51
Organizations
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• Berry_CruncH357
• Hupsaiya 94
• Sammyuel 44
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2194
League of Legends
• Lourlo1348
• Stunt475
Upcoming Events
RSL Revival
2h 56m
Clem vs Classic
SHIN vs Cure
FEL
4h 56m
WardiTV European League
4h 56m
BSL: ProLeague
10h 56m
Dewalt vs Bonyth
Replay Cast
1d 16h
Sparkling Tuna Cup
2 days
WardiTV European League
2 days
The PondCast
3 days
Replay Cast
3 days
RSL Revival
4 days
[ Show More ]
Replay Cast
4 days
RSL Revival
5 days
FEL
5 days
RSL Revival
6 days
FEL
6 days
FEL
6 days
Liquipedia Results

Completed

BSL 2v2 Season 3
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
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 © 2025 TLnet. All Rights Reserved.