• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 11:46
CEST 17:46
KST 00:46
  • 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
Serral wins EWC 202517Tournament Spotlight: FEL Cracow 20259Power Rank - Esports World Cup 202580RSL Season 1 - Final Week9[ASL19] Finals Recap: Standing Tall15
Community News
[BSL 2025] H2 - Team Wars, Weeklies & SB Ladder2EWC 2025 - Replay Pack2Google Play ASL (Season 20) Announced28BSL Team Wars - Bonyth, Dewalt, Hawk & Sziky teams10Weekly Cups (July 14-20): Final Check-up0
StarCraft 2
General
#1: Maru - Greatest Players of All Time Greatest Players of All Time: 2025 Update Serral wins EWC 2025 Power Rank - Esports World Cup 2025 EWC 2025 - Replay Pack
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament FEL Cracov 2025 (July 27) - $10,000 live event TaeJa vs Creator Bo7 SC Evo Showmatch Esports World Cup 2025 $25,000 Streamerzone StarCraft Pro Series announced
Strategy
How did i lose this ZvP, whats the proper response
Custom Maps
External Content
Mutation # 484 Magnetic Pull Mutation #239 Bad Weather Mutation # 483 Kill Bot Wars Mutation # 482 Wheel of Misfortune
Brood War
General
Google Play ASL (Season 20) Announced Shield Battery Server New Patch BW General Discussion [BSL 2025] H2 - Team Wars, Weeklies & SB Ladder BGH Auto Balance -> http://bghmmr.eu/
Tourneys
[Megathread] Daily Proleagues [BSL20] Non-Korean Championship 4x BSL + 4x China CSL Xiamen International Invitational [CSLPRO] It's CSLAN Season! - Last Chance
Strategy
Does 1 second matter in StarCraft? Simple Questions, Simple Answers Muta micro map competition [G] Mineral Boosting
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Total Annihilation Server - TAForever [MMORPG] Tree of Savior (Successor of Ragnarok) Path of Exile
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 UK Politics Mega-thread Russo-Ukrainian War Thread Stop Killing Games - European Citizens Initiative Things Aren’t Peaceful in Palestine
Fan Clubs
INnoVation Fan Club SKT1 Classic Fan Club!
Media & Entertainment
Anime Discussion Thread [\m/] Heavy Metal Thread Movie Discussion! [Manga] One Piece Korean Music Discussion
Sports
2024 - 2025 Football Thread Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 NBA General Discussion
World Cup 2022
Tech Support
Gtx660 graphics card replacement Installation of Windows 10 suck at "just a moment" Computer Build, Upgrade & Buying Resource Thread
TL Community
TeamLiquid Team Shirt On Sale The Automated Ban List
Blogs
Ping To Win? Pings And Their…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Eight Anniversary as a TL…
Mizenhauer
Customize Sidebar...

Website Feedback

Closed Threads



Active: 708 users

Math puzzle #1

Blogs > LastPrime
Post a Reply
LastPrime
Profile Blog Joined May 2010
United States109 Posts
September 09 2010 22:16 GMT
#1
Several schools participated in a tennis tourney. Each player played every player from different school than his/her own. The total number of girls participating differed from the total number of boys by at most 1. Also, the total number of same sex matches differed from the total number of opposite sex matches by at most 1. What is the maximum number of schools that could have sent an odd number of players?

BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
September 09 2010 22:32 GMT
#2
Infinite, if we can control the variables to our liking.

School 1: sends x boys, x+1 girls.
School 2: sends x+1 boys, x girls.

No problem.

Add School 3: sends x boys, x+1 girls.

This would actually break the rule, because the girl plays 2 more boys than girls.

This is fixed by adding School 4: sends x+1 boys, x girls.

If we're out of schools, then just make School 3 send an even number of girls and boys.

In short, an even number of schools can send an odd number of players. The maximum even number is.... .... ....
Compilers are like boyfriends, you miss a period and they go crazy on you.
LastPrime
Profile Blog Joined May 2010
United States109 Posts
September 09 2010 22:47 GMT
#3
Ok, based on what you said, let's take for example the following:

School #--Boy--Girl
1-----------1------2
2-----------2------1
3-----------1------2
4-----------2------1

Same sex matches: 1(2+1+2)+2(1+1+2)+1(1+2+2)+2(1+2+1))/2 + 1(2+1+2)+2(1+1+2)+1(1+2+2)+2(1+2+1))/2. That's 26.

Opposite sex matches: 1(1+2+1)+2(2+2+1)+1(2+1+1)+2(2+1+2)
That's 28.

In fact if you do this out algebraically you get that # of same sex matches in this scenario is 12x^2+12x+2, while the # of opposite sex matches is 12x^2+12x+4.

TanGeng
Profile Blog Joined January 2009
Sanya12364 Posts
Last Edited: 2010-09-09 23:20:42
September 09 2010 23:06 GMT
#4
If School n has even number of players then
Bn (boys) = Gn (girls)

If School n had odd number of players then
Bn = Gn +/- 1
and
Gn-Bn = -1, 0, 1 (three possibilities)

we also have
Bt = sum(Bn) over all n
Gt = sum(Gn) over all n

total difference in same sex vs opposite sex matches is (double counted)
DIFFt = sum( Bn(Bt - Bn) + Gn(Gt - Gn) - Bn(Gt - Gn) - Gn(Bt - Bn) ) over all n
DIFFt = sum( (Gn-Bn) (Gt-Gn -Bt + Bn) ) over all n
DIFFt = sum( (Gn-Bn) ((Gt - Bt) - (Gn - Bn))) over all n
Gt - Bt = sum (Gn - Bn) over all n

DIFFt = sum ((Gn-Bn) ^ 2) - (sum(Gn-Bn))^2 over all n

now Gn - Bn has range -1, 0, 1
and when Gn - Bn the summation term reduces to 0.
Only interesting points are when Gn - Bn is not equal to zero or when school has odd number players
let's call this count Z.

Since (Gn-Bn)^2 = 1 for all interesting points

sum ((Gn-Bn) ^ 2) = Z

DIFFt = Z - (sum(Gn-Bn))^2 with Z values of either 1 or -1

if DIFFt needs to be +/- 1 then Z must be +/- of a perfect square, and Z must match the perfect square in evenness or oddness. That means Z has to be the perfect square itself.

edit: oops I forgot the double counting part, so Z is a perfect square or +/- 2.


example of with 4 odds (2^2)
0 1
0 1
0 1
1 0

3 same sex matches 3 cross sex matches

example with 6 odds (2^2 + 2)
0 1
0 1
0 1
1 0
0 1
1 0

7 same sex matches 8 cross sex matches
Moderator我们是个踏实的赞助商模式俱乐部
Steve496
Profile Joined July 2009
United States60 Posts
Last Edited: 2010-09-09 23:10:22
September 09 2010 23:09 GMT
#5
3.

Let the number of boys sent by each school by b_1, b_2, ... b_n, the number of girls sent by each be g_1, g_2, ... g_n, and the total number of each gender be B and G (respectively).

We know (B-G)^2 = 0 or 1.

Each of b_1 boys plays B-b_1 same-sex games, and G-g1 opposite-sex ones; the girls do this in reverse. Adding this for all schools, we find that the boys play (B^2 - (b_1^2+...+b_n^2))/2 same-sex games, girls the same thing with gs, and there are BG-(b_1*g_1+...+b_n*g_n) opposite sex games, and the difference between those is +/- 1. Rearranging, we get
(B-G)^2-(b_1-g_1)^2-(b_2-g_2)^2-...-(b_n-g_n)^2 = +/- 2. So, 0 or 1, minus a lot of terms that can't be negative, equals +/- 2. Hence, "most" of those terms must have b_k=g_k and thus an even number of students; at most 3 of them can be nonzero, giving us 1 -1 -1 -1 = -2. This is achieved, for instance, when there are three schools, each sending 1 student, 2 of which are boys and one of which is a girl; total students are 2 vs 1, and there is one same-sex and 2 opposite-sex games.
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
September 09 2010 23:10 GMT
#6
Okay. A simpler way of looking at it:

Each school sends 1 boy or 1 girl. Then, we can construct a table like this:

         boy girl
school 1: 0 1
2: 1 0
3: 0 1
4: 1 0
5: 0 1
...

We can then easily see that each player plays every other student in the event, which necessarily means one more opposite-sex match than same-sex match (the students don't play themselves). Adding students to schools doesn't help, because that just serves to increase the discrepancy.

It looks like two schools can send an odd number of students.
Compilers are like boyfriends, you miss a period and they go crazy on you.
rasnj
Profile Joined May 2010
United States1959 Posts
Last Edited: 2010-09-09 23:13:10
September 09 2010 23:12 GMT
#7
EDIT: See Steve496 posted essentially the same solution as me.

Dunno if this kind of thing deserves a spoiler tag, but better be safe:
+ Show Spoiler +

The answer is 3.

Let us number the schools 1,2,...,n.

Let bi denote the number of boys send from school i.
Let gi denote the number of girls send from school i.
Let B denote the total number of boys and let G denote the total number of girls.
Let ki = bi - gi.

For an arbitrary boy from school i he has to play against (B-bi) boys, and (G-gi) girls (similar formulas hold for girls). Thus school i participate in precisely
SSMi = bi(B-bi) + gi(G-gi)
Same-sex matches and
OSMi = gi(B-bi)+bi(G-gi)
Opposite-sex matches.
Every same-sex match is counted in exactly two SSMi (once for each school sending a participant), and similarily for opposite-sex matches. Thus the total number of same-sex matches is:
SSM=(SSM1 + SSM2 + .... + SSMn)/2
The total number of opposite-sex matches is:
OSM = (OSM1 + OSM2 + ....+ OSMn)/2
We have,
SSMi - OSMi = (bi-gi)(B-G) - (bi-gi)^2
Which gives us:
2(SSM-OSM) = (B-G)^2 - (b1-g1)^2 - (b2-g2)^2 - ... - (bn-gn)^2
= k1^2 + k2^2 + k3^2 + ....+kn^2
We assumed SSM-OSM and B-G are both in the set {-1,0,1} so
(B-G)^2 - 2(SSM-OSM) = k1^2 + k2^2 + k3^2 + ....+kn^2
can only take on the values -3,-2,-1,0,1,2,-3. In particular at most three of the values k1, k2, ..., kn are non-zero. Since we haven't imposed an order on the schools we may order them such that k4,...,kn are 0. Then schools k4,...,kn sends an equal number of boys and girls and therefore an even number of players (2bi = 2gi for school i, where i > 3). We have now shown that at most 3 schools can send an odd number of players. To see that this can be achieved we can just let there be 3 schools and let them send:
School 1: 1 boy, 0 girls.
School 2: 1 boy, 0 girls.
School 3: 0 boys, 1 girl.
Then there is 1 same-sex match (between school 1 and 2), and 2 opposite sex matches (1 vs 3 and 2 vs 3).
LastPrime
Profile Blog Joined May 2010
United States109 Posts
September 09 2010 23:19 GMT
#8
On September 10 2010 08:09 Steve496 wrote:
3.

Let the number of boys sent by each school by b_1, b_2, ... b_n, the number of girls sent by each be g_1, g_2, ... g_n, and the total number of each gender be B and G (respectively).

We know (B-G)^2 = 0 or 1.

Each of b_1 boys plays B-b_1 same-sex games, and G-g1 opposite-sex ones; the girls do this in reverse. Adding this for all schools, we find that the boys play (B^2 - (b_1^2+...+b_n^2))/2 same-sex games, girls the same thing with gs, and there are BG-(b_1*g_1+...+b_n*g_n) opposite sex games, and the difference between those is +/- 1. Rearranging, we get
(B-G)^2-(b_1-g_1)^2-(b_2-g_2)^2-...-(b_n-g_n)^2 = +/- 2. So, 0 or 1, minus a lot of terms that can't be negative, equals +/- 2. Hence, "most" of those terms must have b_k=g_k and thus an even number of students; at most 3 of them can be nonzero, giving us 1 -1 -1 -1 = -2. This is achieved, for instance, when there are three schools, each sending 1 student, 2 of which are boys and one of which is a girl; total students are 2 vs 1, and there is one same-sex and 2 opposite-sex games.


We have a winner.
Please log in or register to reply.
Live Events Refresh
Next event in 14m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Hui .404
mouzHeroMarine 348
Rex 28
BRAT_OK 8
StarCraft: Brood War
Bisu 3784
Horang2 3101
Shuttle 2976
Flash 2366
EffOrt 912
Mini 859
Jaedong 696
BeSt 674
Zeus 376
Snow 268
[ Show more ]
Larva 254
Soma 247
ggaemo 186
Hyun 182
ZerO 158
Soulkey 157
Mind 140
Rush 131
Stork 112
Shine 106
Dewaltoss 78
Sharp 78
Killer 64
ToSsGirL 47
[sc1f]eonzerg 46
Aegong 45
soO 43
Movie 40
JYJ40
PianO 39
Sea.KH 39
sorry 32
scan(afreeca) 25
Terrorterran 21
Sacsri 20
Shinee 19
yabsab 15
IntoTheRainbow 5
Stormgate
RushiSC42
Dota 2
Gorgc7229
qojqva3417
XcaliburYe510
Counter-Strike
fl0m3742
sgares328
markeloff94
Super Smash Bros
Liquid`Ken6
Other Games
singsing2092
B2W.Neo466
Fuzer 460
crisheroes395
Happy360
Lowko323
Mlord231
XaKoH 176
QueenE65
Trikslyr45
ZerO(Twitch)17
Organizations
StarCraft: Brood War
UltimateBattle 1896
StarCraft 2
WardiTV44
StarCraft: Brood War
Kim Chul Min (afreeca) 5
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 19 non-featured ]
StarCraft 2
• Berry_CruncH109
• davetesta41
• poizon28 39
• tFFMrPink 18
• LaughNgamezSOOP
• AfreecaTV YouTube
• sooper7s
• intothetv
• Migwel
• Kozan
• IndyKCrew
StarCraft: Brood War
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• C_a_k_e 3932
• WagamamaTV624
League of Legends
• Nemesis4696
• Jankos1204
• TFBlade819
Upcoming Events
WardiTV European League
14m
PiGosaur Monday
8h 14m
OSC
20h 44m
uThermal 2v2 Circuit
1d
The PondCast
1d 18h
Online Event
2 days
Korean StarCraft League
3 days
CranKy Ducklings
3 days
Online Event
4 days
Sparkling Tuna Cup
4 days
Liquipedia Results

Completed

BSL 20 Non-Korean Championship
FEL Cracow 2025
Underdog Cup #2

Ongoing

Copa Latinoamericana 4
Jiahua Invitational
BSL 20 Team Wars
CC Div. A S7
IEM Cologne 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25

Upcoming

BSL 21 Qualifiers
ASL Season 20: Qualifier #1
ASL Season 20: Qualifier #2
ASL Season 20
CSLPRO Chat StarLAN 3
BSL Season 21
RSL Revival: Season 2
Maestros of the Game
SEL Season 2 Championship
WardiTV Summer 2025
uThermal 2v2 Main Event
HCC Europe
Yuqilin POB S2
ESL Pro League S22
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
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.